Размен монет или Незадача с сантиками

[Ktina]

Всем доброго времени суток!
Прошу меня простить за почти четырёхмесячное отсутствие, вернее, пассивное присутствие (если не считать несколько моих сообщений в "Свободном полёте").
Возникла необходимость в овладении базовым уровнем арабского языка, а на это нужны были время и силы.

Итак, задача.
В государстве имеют хождение монеты в 1, 2, 3, 5, 8, 10, 15, 20, 25, 32, 50, 57, 75, 100 сантиков. Автомат разменивает одну монету на четыре других (например, монету в 100 сантиков на монеты в 57, 20, 20 и 3 сантика). Можно ли за несколько разменов превратить одну монету в 100 сантиков в 100 монет по 1 сантику?
(Ленинградская олимпиада, 2004, районный тур).

Если ответ на задачу положителен, то последним разменом должен быть размен на 4 монеты по одному сантику. Только вот нет такой монеты, которую можно было бы так разменять.

Или я опять условие задачи не понимаю?

[iifat]

Не очень понятно, что будет делать злосчастный автомат, если ему сунуть $1,2,3$ сантима...

Ktina в сообщении #1034006 писал(а):

базовым уровнем арабского языка

Эээ... Почти четыре месяца... И, стесняюсь спросить, как? Нет, — как?

[atlakatl]

Если заменить условие на "Автомат разменивает одну монету не более чем на четыре других", то решение тривиально.
Что-то автор другое имел ввиду. Особо смущает наличие монеты в 57 сантиков. Не "десятичная" она какая-то. И может использоваться только при первом размене.
Предлагаю негативный вариант задачи:
Размен всегда на 4 монеты. Определить наименьшее число этапов размена, когда автомат "заклинит", - из-за невозможности размена дальнейшего.

[atlakatl]

atlakatl в сообщении #1034039 писал(а):

Размен всегда на 4 монеты

Уточняю: монеты номиналом 1, 2, 3 автомат не заклинивают, а ссыпаются в приёмный лоток, в дальнейшем размене не участвуя.

[Ktina]

iifat в сообщении #1034034 писал(а):

Ktina в сообщении #1034006 писал(а):

базовым уровнем арабского языка

Эээ... Почти четыре месяца... И, стесняюсь спросить, как? Нет, — как?

В личку, пожалуйста.

-- 06.07.2015, 08:38 --

iifat в сообщении #1034034 писал(а):

Не очень понятно, что будет делать злосчастный автомат, если ему сунуть $1,2,3$ сантима...

И мне непонятно. Получается, необходимо избегать девушек и трёшек, если мы всё ещё лелеем мечту разменять 100 по 1. Но тогда не может быть и монеты в 5 сантиков (её без 2 и 3 не разменять), а также в 8, 10, 15... в общем, и так далее. Короче, никаких монет не божет мыть. Нет, что-то здесь не то.
Вот ссылка на задачу:
http://orc.csu.ru/ZadOlimp/SP/reg04.pdf
(стр. №2, задача №3)

[iancaple]

По смыслу задачи автомат должен учитывать клиентские пожелания, например как он иначе выберет между многими вариантами размена 8=2+2+2+2=5+1+1+1=...
Это может быть реализовано либо кнопками с фиксированным смыслом, обозначенным рядом с каждой, либо полноценной клавиатурой с дисплеем, второе, конечно, питерским школьникам 2004 года ближе.
Думаю, что решение ТС верно и скорей всего совпадает с решением жюри. Для большей перестраховки впереди еще можно добавить фразу: "Если автомат допускает размен "с убытком", например 5 на 1+1+1+1, в данной задаче не должно быть ни одной разменной операции с убытком"

[Ktina]

iifat
atlakatl
iancaple
Спасибо!