№ 2311. Авторские варианты - ЕГЭ по информатике

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены буквами:

A. Умножить на 4

B. Прибавить 2
C. Умножить на 3

Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 6 в число 666, и при этом траектория содержит ровно 66 различных чисел, не включая начального и конечного числа?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAC при исходном числе 6 траектория будет состоять из чисел 8, 32, 96.

Ответ
Python

130

from functools import lru_cache


@lru_cache(None)
def f(x, y, cnt=0):
    if x == y and cnt == 66:
        return 1
    if x > y:
        return 0
    return f(x * 4, y, cnt + 1) + f(x + 2, y, cnt + 1) + f(x * 3, y, cnt + 1)


print(f(6, 666))