Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Олимпиадные задачи на английском языке

04/02/2008 | Зима 2008 дорешивание (1m) |

04/02/2008 | Тренировка (задачи CTU Open Contest 2007) (m) |

*Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Have you ever experienced similar situations? Paying a precise amount can sometimes be difficult, if the set of available coins and banknotes ("tenders") is limited. The situation above was
finally solved: The customer paid 200+1 crowns, got 100+0.50 back, paid another 0.20+0.20,
and finally got 0.10 back. This means, 7 tenders had to be exchanged. Sometimes, it may be
even more complicated. Your task is to write a program that solves situations like this.

Input contains several tasks to be solved. Each task begins with a line containing one non-negative number: the amount to be paid. Then there is a list of tenders possessed by the
customer (the one who pays). Each line in the list contains the tender nominal value (non-negative number), one space, number of tenders of that value (non-negative integer), and the
lowercase letter `"x"`. The list is terminated by a line containing number `"-1"`.

After the first list, there is a list of tenders possessed by the shopkeeper (the one who gets paid).
The second list has the exactly same format as the first one.

Then the next task begins. The last task is followed by one more line containing `"-1"`.

You may assume that each list will contain at most 100 lines, and nobody will have more than
`10\ 000` units and/or 500 tenders. Nominal values can be arbitrary, they do not need to follow
any existing scheme valid in known countries. All numbers that allow non-integer values will be
given either as integers or as decimal numbers with one or two digits after the decimal point.

For each task, output one line containing the sentence "``X` tenders must be exchanged.`",
with `X` replaced by the minimal number of tenders that are to be used to pay the required
amount. If this is not possible at all, output the sentence "`The payment is impossible.`"
instead.

Sample Input

100.80 500 1x 200 3x 1.00 10x 0.20 2x -1 500 10x 200 12x 100 8x 0.10 1x 0.20 0x 0.50 100x 20 2x -1 200 10 19x -1 200 1x -1 -1

Sample Output

7 tenders must be exchanged. The payment is impossible.