TopCoder problem "PayBill" used in SRM 219 (Division II Level Three)



Problem Statement

    

You have just finished your delicious Chinese food dinner with your friends, and divided up the bill. You are given the int[] meals, where each element of meals is the total amount owed by a given person. The number of elements in meals is the same as the number of people who ordered dinner. You also notice that there is totalMoney that has been placed on the table.

You now need to determine, based upon the price of each person's meal, and the amount of money that has been paid, which of your friends has paid. You are to return a int[] indicating who has already paid, where the value of each element is the zero-based index of a given person. The return int[] should be sorted in ascending order. The given data will be such that exactly one unique solution is possible.

 

Definition

    
Class:PayBill
Method:whoPaid
Parameters:int[], int
Returns:int[]
Method signature:int[] whoPaid(int[] meals, int totalMoney)
(be sure your method is public)
    
 

Constraints

-meals will contain between 1 and 50 elements, inclusive.
-Each element of meals will be between 1 and 10000, inclusive.
-totalMoney will be between 0 and 500000, inclusive.
-There will be exactly one unique solution to the problem.
 

Examples

0)
    
{ 1000, 1200, 1300 }
2500
Returns: { 1,  2 }
Clearly, the only way there can be 2500 on the table is if person 1 and 2 have paid, but person 0 has not.
1)
    
{ 100, 200, 350 }
300
Returns: { 0,  1 }
Of course, 100 + 200 = 300.
2)
    
{ 150, 200, 350, 400 }
900
Returns: { 0,  2,  3 }
Here, we have 150 + 350 + 400 = 900.
3)
    
{6584,6733,6018,5840,2723,4902,4260,
 5375,6745,1234,3000,8222,2472,
 4348,1716,9995,415,1234,2345,5679}
70630
Returns: { 0,  1,  3,  4,  5,  6,  8,  9,  11,  13,  14,  15,  16,  17,  19 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3114

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5865&pm=3114

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming