Алгоритм решения задания 14. Часть 1
Учимся решать 15 задания первого типа
Читать
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Умножить на 3
B. Умножить на 2
C. Прибавить 15
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 1208, и при этом траектория содержит не более двух команд А, не менее трёх команд B и ровно 10 команд C.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAC при исходном числе 2 траектория будет состоять из чисел 4, 12, 27.
Правильный ответ:
28
from functools import lru_cache
@lru_cache(None)
def f(x, y, a=0, b=0, c=0):
if x == y and a <= 2 and b >= 3 and c == 10:
return 1
if x > y:
return 0
return (f(x * 3, y, a + 1, b, c) +
f(x * 2, y, a, b + 1, c) +
f(x + 15, y, a, b, c + 1))
print(f(1, 1208))
