Connection Status:
Competition Arena > PayBill

PayBill

SRM 219 · 2004-11-20 · by erinn

SRM 219 · 2004-11-20 · by erinn · Dynamic Programming
Class Name: PayBill
Return Type: int[]
Method Name: whoPaid
Arg Types: (vector<int>, int)
Problem Statement

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.

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 }
4)
{3,5,6,7}
10
Returns: { 0,  3 }

Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PayBill with a public method vector<int> whoPaid(vector<int> meals, int totalMoney) · 23 test cases · 2 s / 256 MB per case

Submitting as anonymous