Советские монеты

[Ktina]

В СССР были монеты достоинством 1, 2, 3, 5, 10, 15, 20, 50 копеек и один рубль. Автомат разменивает любую монету, начиная с 5 копеек, на четыре монеты. На какое наибольшее число монет можно наверняка разменять монету, достоинством 1 рубль?

[gris]

Что значит — наверняка? Я помню эти автоматы. Сунешь гривенник, а он тебе выдаст три по три и копейку. А если повезёт — пятак, две двушки и копейку. Пятак-то всегда меняют на двушку и три копейки. Всего семь монет, а не три. Пятнашку тоже то на восемь, то на девять монет меняют. А то и на семь. Зато газировки выдуешь три стакана. То есть получается, что "наверняка" это наименьшее количество неразменных монет? Голову сломаешь.

[Red_Herring]

gris
Монеты советские, автомат буржуйский. Причем думает: «менять гривенник по пятаку, алтыну и два раза по копейке, так этот гад пятак обратно засунет; не, я ему либо два раза по алтыну и два раза по двушке (чтоб воду пил и деффке звонил) или три раза по алтыну и копеечку (чтоб упился) выдам».

[gris]

Red_Herring, знаем мы, какой у ТС автомат. Там Аллочка с Ксю так вам наменяют, что ещё должны окажетесь.
У меня выходило 48 монет: 26 с сиропом и 22 без сиропа. Звонить нельзя. Так это чтож получается: на рупь почти 10 литров газировки? Ничосе коммунизьм.

[Yadryara]

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

Автомат разменивает любую монету, начиная с 5 копеек, на четыре монеты.

Имеется в виду ровно на четыре монеты?

[Iam]

Последовательно оцените $N(i)$ для каждой монеты: $N(1)=N(2)=n(3)=1, N(5)=n(10)=4, N(15)=7, \dots, N(100)=46$.

[Yadryara]

Если ровно на четыре, тогда можно так.

Меняем рупь: $10 + 20 + 20 + 50 = 100$

Меняем полтинник: $ 5 + 5 + 20 + 20 = 50$

Меняем все $4$ двадцатки: $ 5 + 5 + 5 + 5 = 20$

Меняем единственный гривенник: $ 1 + 1 + 3 + 5 = 10$ либо $ 1 + 2 + 2 + 5 = 10$

Меняем все $19$ пятаков: $ 1 + 1 + 1 + 2 = 5$ и получаем $57$ газировок и $19$ двушек.

Итого $59$ газировок, $19$ звонков и 1 сироп. Всего 79 монеток, даже если кто-то найдёт в себе мужество отказаться от сиропа

[EUgeneUS]

Yadryara
Автомат злобный, и совсем не обязательно разменяет полтинник $ 5 + 5 + 20 + 20 = 50$, может и так: $ 10 + 10 + 15 + 15 = 50$.

[Yadryara]

EUgeneUS
Я в курсе, что есть два способа разменять рупь, четыре способа — полтинник, четыре — двадцатку, три — пятнашку и четыре — десятку.

Да, в условии ещё есть важное слово "наверняка". Если в смысле "гарантированно", то да, надо пересчитывать.

[Sender]

У меня получилось 46.
5 копеек всегда размениваются на 4 монеты,
10 хитрый автомат тоже разменяет на 4: $10=3+3+3+1,$
15 на 7: $15=10+3+1+1,$
20 на 10: $20=15+3+1+1,$
50 на 22:$50=15+15+10+10,$
Рубль на 46: $100=50+20+20+10=50+20+15+15.$

-- Пн июн 19, 2017 10:23:17 --

О, не заметил.

Iam в сообщении #1226992 писал(а):

Последовательно оцените $N(i)$ для каждой монеты: $N(1)=N(2)=n(3)=1, N(5)=n(10)=4, N(15)=7, \dots, N(100)=46$.

[PETIKANTROP]

Вообще, в советские времена в метро стояли автоматы по размену 20, 15 и 10-копеечных монет по 5 копеек, а на почтах - по 2 копейки. Они служили жетонами. И все! Современные разменные автоматы снабжены функцией, по которой пользователь получает размен монетами заданного номинала. Т.е. аппарат должен быть снабжен примерно равным запасом монет разного достоинства. В представленной Ktina задаче ничего не сказано ни про "вредный ум" аппарата, ни про лимит монет на размен. Следовательно однозначного решения быть не может.

[Red_Herring]

PETIKANTROP в сообщении #1227106 писал(а):

В представленной Ktina задаче ничего не сказано ни про "вредный ум" аппарата

Сказано, словом наверняка

[gris]

То есть это типа "минимакс" получается? Наибольшее количество монет при гадском поведении автомата. Интересно, а что будет "максимином"? Наименьшее количество монет, если автомат старается выдать их побольше? Правда, тут надо потребовать, чтобы юзер менял всё до конца, а то зажмёт рубль в потном кулачке и выиграет. Тогда получается, что от юзера ничего не зависит. Как и в первом случае.

[EUgeneUS]

gris
Ага, от юзера ничего не зависит, считается, что юзер меняет до конца.

gris в сообщении #1227123 писал(а):

Интересно, а что будет "максимином"?

"Максимином" будет 42 79. Число монет, на которые разменяет рубль автомат, максимизирующий количество монет.

[Iam]

EUgeneUS в сообщении #1227148 писал(а):

"Максимином" будет 42 79. Число монет, на которые разменяет рубль автомат, максимизирующий количество монет.

Максимальным числом монет, конечно, будет 79. Но почему "максимин"? Минимума, похоже, здесь никакого нет.