Kodemonk

STAMPS – Stamps

Problem:

Everybody hates Raymond. He’s the largest stamp collector on planet earth and because of that he always makes fun of all the others at the stamp collector parties. Fortunately everybody loves Lucy, and she has a plan. She secretly asks her friends whether they could lend her some stamps, so that she can embarrass Raymond by showing an even larger collection than his. Raymond is so sure about his superiority that he always tells how many stamps he’ll show.And since Lucy knows how many she owns, she knows how many more she needs. She also knows how many friends would lend her some stamps and how many each would lend. But she’s like to borrow from as few friends as possible and if she needs too many then she’d rather not do it at all. Can you tell her the minimum number of friends she needs to borrow from?

Read More Here


Hint: You have to collect at least x Rs  with some given coins , where coins can be of different amount. Which coin you pick first?


Code:


#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

int main() {
	lli T,count=0;
	cin>>T;
	while(T--){
	   count++;
	   lli required,tFriends;
	   cin>>required>>tFriends;
	   
	   vector<lli> vec(tFriends);
	   lli sum=0;
	   for(int i=0;i<tFriends;i++){ cin>>vec[i];
	       sum += vec[i];
	   }
	   if(sum < required){
	       cout<<"Scenario #"<<count<<":\nimpossible\n\n";
	       continue;
	   }
	   
	   sum=0;
	   sort(vec.begin(),vec.end(),greater<lli>());
	   int i=0;
	   while(sum < required)
	        sum+=vec[i++];
	   cout<<"Scenario #"<<count<<":\n"<<i<<"\n\n";
	}
	return 0;
}


Explanation: As suggested in hint, we first sort the input vector and start picking the largest item until sum of picked number is less then required sum.

we can also solve above problem in time O(n + k.log n) using max-heap where kis the minimum number of friends required for a given instance of above problem. First we create a max-heap of all elements, then start removing the maximum element until sum of removed elements is less then the required sum.

 

Not clear about which data structure will be best for given Scenario? Try this book Introduction to Algorithms

 

 

Share This:

Next Post

Previous Post

© 2017 Kodemonk

Theme by Anders Norén