Can someone suggest algo or hint of this!

http://codeforces.com/problemset/gymProblem/100989/H
question name queue A

I think it is a variation of famous Coin Change problem. You can google about it. Break the problem in 2 cases.

Case 1 is when student pays exact amount. It is direct one. Keep track of each type of notes cashier has. Increment these notes in amount cashier has.

Case 2 is when student pays more. In this case student has one note which has larger amount than requited. If we remove this note then student will not be able to pay. All notes except this one are good to go.

In this case try if you can remove that extra value note and give it to cashier. Now make cashier try to bring equal amount value from notes cashier has equal to deficiency of total pay.

In this also try to keep smaller value notes for cashier and give bigger value notes to students so that in future if some student wants smaller value note we would be able to exchange it.

eg. suppose student pays notes worth extra 20, and cashier has notes like 20, 0, 0,1,0. Pay the 20 one. If you pay from notes of 1, it will be like 0,0,0,1,0. Now if some student want to exchange for 15, it is not possible. If you exchange 20 one, we can exchange 15 later on.

Learn about coin change- dynamic programming.


Specifically look for the part when he backtracks which coins are used to make that sum of value.

Figure out remaining part on your own. Haven’t solved it. Having exams tomorrow still replying at 5AM :slight_smile: Sorry for typos.

3 Likes

You actually don’t need any standard algorithms like coin change or any other variation of DP for this problem.

Initialise an array of size 5 with each element 0, that keeps track of current number of notes of each type that cashier have .

Now every time, a new person comes to cashier, add his notes to the array accordingly.
Also, calculate the amount he gave to cashier and subtract the amount he was actually expected to pay.
Now, if this difference can be obtained by the notes of cashier , then we update our array.
Note: Cashier will try to give the amount by paying the higher denotions first.
That is, if he has 2 notes of 5 and 10 notes of 1, and if he has to pay back Rs 10, he will pay by 2 notes of 5.
Hope that helps.
You can refer to this solution for implementation.

#include<bits/stdc++.h>using namespace std; int main(){	int n;	cin>>n;	int arr[n][6];	for(int i=0;i<n;i++)	{		for(int j=0;j<6;j++)			cin>>arr[i][j];	}	// cout<<"yes\n";	int array[6];	memset(array,0,sizeof(array));	int array2[6];	array2[0]=0;	array2[1]=1;	array2[2]=5;	array2[3]=10;	array2[4]=20;	array2[5]=50;	int flag=0;	for(int i=0;i<n;i++)	{		int c=arr[i][0];		int c1=0;		for(int j=1;j<6;j++)		{			c1=c1+(array2[j]*arr[i][j]);			array[j]=array[j]+arr[i][j];		}		if(c1!=c)		{			int req=c1-c; 			while(req>=array2[5])			{				if(array[5]>0)				{					req=req-array2[5];					array[5]--;				}				else					break;			}			while(req>=array2[4])			{				if(array[4]>0)				{					req=req-array2[4];					array[4]--;				}				else					break;			}			while(req>=array2[3])			{				if(array[3]>0)				{					req=req-array2[3];					array[3]--;				}				else					break;			}			while(req>=array2[2])			{				if(array[2]>0)				{					req=req-array2[2];					array[2]--;				}				else					break;			}			while(req>=array2[1])			{				if(array[1]>0)				{					req=req-array2[1];					array[1]--;				}				else					break;			} 			if(req>0){				flag=1;				break;			}		}	}	if(flag==1)		cout<<"no\n";	else		cout<<"yes\n";
}
2 Likes