Бочка

Районная олимпиада школьников Удмуртии по программированию, 2009 год

У нас есть бочка емкостью 200 литров. И есть вёдра ёмкостью 1, 4, 7 и 9 литров.

Требуется набрать в бочку указанное количество литров воды. Но река далеко и нужно максимально уменьшить количество походов за водой. За один раз можно приносить только одно ведро. Выливать воду мимо бочки нельзя. Нельзя также переливать воду в другие вёдра. В бочке должно оказаться ровно столько воды, сколько требуется.

Технические требования

Написать программу, которая показывает, в каком порядке нужно приносить вёдра с водой. Достаточно выдать любой из вариантов, где количество походов минимально.

Формат ответа

<Количество походов>: <кол-во походов с ведром 9 литров>, <кол-во походов с ведром 7 литров>, <кол-во походов с ведром 4 литра>, <кол-во походов с ведром 1 литр>

Пример

Сколько нужно налить: 38

Ответ: 5: 3, 1, 1, 0

 

Добавить комментарий