Районная олимпиада школьников Удмуртии по программированию, 2009 год
У нас есть бочка емкостью 200 литров. И есть вёдра ёмкостью 1, 4, 7 и 9 литров.
Требуется набрать в бочку указанное количество литров воды. Но река далеко и нужно максимально уменьшить количество походов за водой. За один раз можно приносить только одно ведро. Выливать воду мимо бочки нельзя. Нельзя также переливать воду в другие вёдра. В бочке должно оказаться ровно столько воды, сколько требуется.
Технические требования
Написать программу, которая показывает, в каком порядке нужно приносить вёдра с водой. Достаточно выдать любой из вариантов, где количество походов минимально.
Формат ответа
<Количество походов>: <кол-во походов с ведром 9 литров>, <кол-во походов с ведром 7 литров>, <кол-во походов с ведром 4 литра>, <кол-во походов с ведром 1 литр>
Пример
Сколько нужно налить: 38
Ответ: 5: 3, 1, 1, 0