Dedicate Length

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Greedy algorithm.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT(SIMPLIFIED):

Nikhil wants to bring sofa(s) to his room. But he wants to dedicate the entire length of the room to the sofa(s) (yes I know he is a bit weird).
Now Nikhil’s room length is W meters, and when he went to the shop he found out sofas of two types, one of length N and other of length M.Now, let Nikhil know how many sofas of the first and second type he should buy to reduce wastage of space. First minimize the space wastage then, if similar result arises always prefer the sofa with a larger length. In case N==M give preference to second sofa.

See original problem statement here

For Example :

Input
1
24 3 5

Output
3 3

Nikhil will buy 3 sofas of size 3 and 3 sofa's of size 5.

SOLVING APPROACH:

Since we have to minimize the waste of space, we shall find all possible arrangements and then choose the best one (greedy,right?).

Now you must be thinking that would take exponential time. But no, it won’t.

We shall keep storing the possible combination of each wasted space possible.

Then take the least one!!

SOLUTIONS:

#include <bits/stdc++.h>

     using namespace std;
     typedef long long ll;
     bool cmp1(pair<ll,ll> a,pair<ll,ll> b)
    {
    if(a.first==b.first)
        return a.second>b.second;
    return a.first>b.first;
    }

     bool cmp2(pair<ll,ll> a,pair<ll,ll> b)
    {
    if(a.second==b.second)
        return a.first>b.first;
    return a.second>b.second;
     }
     int main()
    {
    ll t;
    cin>>t;
    while(t--)
    {
     ll w,n,m;
     cin>>w>>n>>m;
     vector<pair<ll,ll> >v[w+1];
     ll so=1;
    if(n>m)
    {
    so=0;
    }
    for(ll i=w/m;i>=0;i--)
    {
        ll l=w-(m*i);
       v[l%n].push_back({l/n,i});

    }
    ll f=1;
    for(ll i=0;i<=w;i++)
    {
      if(v[i].size()>0)
      {
          f=0;
          if(so==0)
          sort(v[i].begin(),v[i].end(),cmp1);
          else
         sort(v[i].begin(),v[i].end(),cmp2);
        cout<<v[i][0].first<<" "<<v[i][0].second<<"\n";
       break;

      }

    }
    if(f==1)
    cout<<"0 0\n";
    }
    return 0;
    }

This article tried to discuss Greedy Algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy Algorithm you can check out MYCODE | Competitive Programming.