ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79408
Темы:    [ Теория алгоритмов (прочее) ]
[ Обратный ход ]
Сложность: 3
Классы: 8
В корзину
Прислать комментарий

Условие

Петя приобрёл в магазине вычислительный автомат, который за 5 к. умножает любое введённое в него число на 3, а за 2 к. прибавляет к любому числу 4. Петя хочет, начиная с единицы, которую можно ввести бесплатно, набрать на автомате число 1981 и затратить наименьшую сумму денег. Во сколько обойдутся ему вычисления? А что будет, если он захочет набрать число 1982?

Решение

Заметим сначала, что на автомате нельзя набрать чётное число. Следовательно, у Пети не получится набрать число 1982.
Лемма. После первого умножения на 3 невыгодно прибавлять 4 более двух раз подряд.
Доказательство леммы. Заменив последовательность действий ×3, + 4, + 4, + 4 на +4, ×3, мы уменьшим затраты.
Теперь можно восстановить последовательность действий Пети, начиная с последнего: если число не делится на 3, то оно было получено прибавлением четвёрки, а если делится, то либо оно было получено умножением на 3, либо при его получении были использованы только прибавления четвёрки. Таким образом получаем, что оптимальная для Пети последовательность действий имеет вид:
+4, + 4, + 4, + 4, + 4, ×3, + 4, + 4, ×3, + 4, ×3, + 4, + 4, ×3, + 4.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 45
Год 1982
вариант
Класс 7
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .