1563 . Tab in Restaurant

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

NTU PK NTU PK 2011

Description

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?

Input Format

The first line of the input file contains an integer T, which is the number of test cases.

The first line of each test case is N, the number of people at the table. This is followed by N lines, one for each i in [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.

You may assume that no person owes more money than they have 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.

Output Format

For each test case, output "YES" if all of the money can be rearranged
so that each person ends up paying the correct amount and "NO" if not.

Sample Input 1

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

Sample Output 1

YES
YES
NO

Hints

Problem Source

Migrated from old NTUJ.

MIT Individual 2008

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7000 65536 200
Submit
Back to Top