Задача 79408
|
|
 |
Условие
Петя приобрёл в магазине вычислительный автомат, который за 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.
