RSTAURNT - Restaurant Tab

no tags 

After eating dinner at a restaurant with some friends, you determine how much money each person owes. Each of you has some cash and some change, but very few of you have exact change. Can you make change for each other so that each person ends up paying the exact right amount?


The input file will contain multiple cases. The first line of each case is N, the number of people at the table. This is followed by N lines, one for each i ∈ [1,N], containing

xi ci,1 ci,5 ci,10 ci,25 ci,100 ci,500 ci,1000 ci,2000 ci,5000 ci,10000

where xi is the amount in cents that person i owes and ci,v is the number of coins or bills worth v cents that person i starts out with. For example, person 1 has c1,1 pennies, c1,5 nickels, etc. Each case is followed immediately by the next case. The end of the input is indicated by a line containing only a zero. You may assume that no person owes more money than they have (i.e. xi ≤ Σj j*ci,j) and that the total amount of money in cents that everyone starts with fits in a signed 32-bit integer. You may also assume that N ≤ 100000.


For each case, output the case number, in the format "Case #:" (where # is the case number, starting at 1), followed by a space, followed by "YES" if all of the money can be rearranged so that each person ends up paying the correct amount and "NO" if not.


10 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0 0
500 0 0 0 0 0 1 0 0 0 0
100 4 0 2 3 0 1 0 0 0 0

Case 1: YES
Case 2: YES
Case 3: NO

hide comments
Minsuk Kim: 2014-11-29 06:25:25

use greedy solution ;)

Added by:Minilek
Time limit:5.986s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2008