Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1418. Restaurant tab
Жадные алгоритмыОлимпиадные задачи на английском языке
| 24/06/2010 | Лето 2010 дорешивание ( 4H) |
| 30/06/2010 | Лето 2010 - 4 (H) |
Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
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
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
`x_i\ c_{i,1}\ c_{i,5}\ c_{i,10}\ c_{i,25}\ c_{i,100}\ c_{i,500}\ c_{i,1000}\ c_{i,2000}\ c_{i,5000}\ c_{i,10000}`
where `x_i` is the amount in cents that person `i` owes and `c_i,v` is the number of coins or bills
worth `v` cents that person `i` starts out with. For example, person 1 has `c_{1,1}` pennies, `c_{1,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. `x_i\ ≤\ ∑_j\ j*c_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`.
Output
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.
Sample Input
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 0
Sample Output
Case 1: YES Case 2: YES Case 3: NO
