eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Change by Mass

Change by Mass

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Your team is working on software for automated check-out machines (such as are found in supermarkets and large home-improvement stores). The usual change-making process for these machines minimizes the number of coins dispensed when dispensing amounts under one dollar. However, a customer wants to change the logic in the machines to minimize the mass of the coins dispensed (to "lighten the load" for their customers). Minimizing the number of coins dispensed remains a secondary goal.

The name, value, and mass of each United States (No, our Canadian friends weren't forgotten. We had to pick only one set of values, though.) coin with a value less than one dollar are as follows:

Half dollar coins may or may not be available, as they do not circulate to the extent of the other coins.

Your team is to write a program that will, given an amount in cents, determine the coins to be dispensed that will minimize the total mass of the dispensed coins, and secondarily minimize the number of coins dispensed.

Входные данные

Input to your program will be a series of change requests, one per line. Each change request will consist of the amount to be dispensed (integer cents, in the range 1-99 inclusive) starting in the first column, followed by a single space and the number of half-dollar coins in the machine (as an integer ≥ 0).

Input will be terminated by the end-of-file.

Выходные данные

x

For each request, your program should produce a line containing the coins to be dispensed. The output line is to show the denominations being dispensed in decreasing order, in the format 'nd' (meaning n coins of denomination d are to be dispensed). For example, 35 cents would be dispensed as '1x25 1x10'. Denomination entries are to be separated from each other by single spaces, and no leading or trailing whitespace is to appear on an output line.

Пример

Входные данные #1
35 1
1 0
18 3
60 0
-1
Выходные данные #1
Request 1: 1x25 1x10
Request 2: 1x1
Request 3: 1x10 1x5 3x1
Request 4: 2x25 1x10
Источник ACM North Central North America Regional Programming Contest, November 12, 2011