Задача ATM
Вам надоели абсолютно неестественные олимпиадные задачи, не так ли? Ну, зачем говорить: «Если бы банкомат заправили банкнотами номиналом 10, 50 и 60 рублей, то сумму 120 следовало б выдавать не как 100+10+10, а как 60+60…» Никто не станет вводить в оборот банкноты номиналом 60… По этой причине сейчас Вам предлагается решить абсолютно практическую задачу.
В обороте находятся банкноты номиналами 1, 2, 5, 10, 20, 50, 100, 200 и 500 гривен. При этом, банкоматы не заправляют банкнотами номиналами 1 грн и 2 грн. Таким образом, в банкомате есть N5 штук банкнот по 5 грн, N10 штук банкнот по 10 грн, N20 штук банкнот по 20 грн, N50 штук банкнот по 50 грн, N100 штук банкнот по 100 грн, N200 штук банкнот по 200 грн и N500 штук банкнот по 500 грн. На банкомат распространяются административное ограничение «выдавать единоразово не более 2000 грн» и техническое ограничение «выдавать единоразово не более 40 банкнот». Последнее ограничение относится к суммарному количеству банкнот (возможно, разного номинала).
Напишите программу, которая будет определять, как выдать необходимую сумму, использовав минимальное количество банкнот (с учетом указанных ограничений).
Технические условия.
Программа ATM читает со стандартного ввода (клавиатуры) сначала количество банкнот N5, N10, N20, N50, N100, N200 и N500, потом сумму S, которую нужно выдать. Все числа входных данных – целые и находятся в пределах от 0 включительно до 5000 включительно.
Программа должна вывести на стандартный выход (экран) семь чисел — количества банкнот по 5 грн, по 10 грн, по 20 грн, по 50 грн, по 100 грн, по 200 грн и по 500 грн. Эти семь чисел нужно вывести в одну строку через пробелы. Сумма этих чисел (общее количество банкнот к выдаче) должна быть минимально возможной. Если выдать сумму, учитывая ограничения, невозможно, программа должна вместо ответа вывести -1.
Примеры
Ввод
0 100 1 100 0 0 0 190
Вывод
0 2 1 3 0 0 0
Ввод
5000 2000 5000 2000 5000 2000 500 17
Вывод
-1