Изменение массы
Ваша команда занимается разработкой программного обеспечения для автоматизированных кассовых аппаратов, которые можно встретить в супермаркетах и крупных магазинах товаров для дома. Обычно такие аппараты выдают сдачу, минимизируя количество монет при суммах менее одного доллара. Однако один из клиентов хочет изменить логику работы аппаратов, чтобы минимизировать массу выдаваемых монет, облегчая тем самым нагрузку для своих клиентов. Минимизация количества монет остается второстепенной задачей.
Ниже приведены название, номинал и масса каждой монеты США с номиналом менее одного доллара:
Название | Значение | Масса |
Цент ("пенни") | 0.01 | 2.500 грамм |
Пять центов ("никель") | 0.05 | 5.000 грамм |
Дайм | 0.10 | 2.268 грамм |
Четверть доллара | 0.25 | 5.670 грамм |
Полдоллара | 0.50 | 11.340 грамм |
Монеты в полдоллара могут быть доступны или нет, так как они не так часто используются, как другие монеты.
Ваша задача — написать программу, которая, получив сумму в центах, определит, какие монеты следует выдать, чтобы минимизировать общую массу, и второстепенно минимизировать количество монет.
Входные данные
Входные данные для программы будут представлять собой серию запросов на сдачу, каждый из которых записан в отдельной строке. Каждый запрос содержит сумму, подлежащую выдаче (целое число в центах от 1 до 99 включительно), начиная с первого столбца, за которым следует один пробел и количество монет в полдоллара, доступных в машине (целое число ≥ 0).
Ввод завершается концом файла.
Выходные данные
Для каждого запроса программа должна выводить строку, содержащую информацию о монетах, которые будут выданы. Строка должна содержать номиналы монет в порядке убывания, в формате 'nd' (где n — количество монет номиналом d). Записи номиналов должны быть разделены одним пробелом, без начальных или конечных пробелов в строке.