Зміна за масою
Вашій команді доручено розробити програмне забезпечення для автоматизованих касових апаратів, які використовуються в супермаркетах та великих магазинах товарів для дому. Зазвичай, ці апарати видають здачу, мінімізуючи кількість монет, що видаються, коли сума менша за один долар. Однак, один з клієнтів хоче змінити цю логіку, щоб мінімізувати масу монет, які видаються, тим самим "полегшуючи навантаження" для своїх клієнтів. Мінімізація кількості монет залишається вторинною метою.
Назва, вартість та маса кожної монети Сполучених Штатів (так, наші канадські друзі не були забуті, але ми повинні були вибрати лише один набір значень) з вартістю менше одного долара є такими:
Назва | Значення | Маса |
Цент ("пенні") | 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). Наприклад, 35 центів буде видано як '1x25 1x10'. Записи номіналів мають бути відокремлені один від одного одним пробілом, і на вихідному рядку не повинно бути жодних початкових або кінцевих пробілів.