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

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

A. Прибавить 2

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

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAC при исходном числе 2 траектория будет состоять из чисел 5, 7, 22.

Ответ
Python

71932

from functools import lru_cache


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


print(f(2, 44))