  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Dedicate Length

Last Updated on March 28, 2022 by Ria Pathak ### CONCEPTS USED:

Greedy algorithm.

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].first<<" "<<v[i].second<<"\n";
break;

}

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

[forminator_quiz id="1473"]

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.