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 using the best javascript tutorials 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;
    }

Previous post REMAINING GOLD COIN
Next post STACK SUM

Leave a Reply

Your email address will not be published. Required fields are marked *