Задание 23. Информатика. ЕГЭ. Поляков-8833

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

1. Прибавь \(1\)
2. Прибавь \(5\)
3. Умножь на \(3\)

Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе \(2\) результатом является \(49,\) при этом траектория вычислений содержит \(18\) или \(30,\) и не содержит чисел \(28\) и \(36?\)

def f(n, targ, deny=(28, 36)):
    if n >= targ:
        return int(n == targ)
    if n in deny:
        return 0
    return f(n + 1, targ, deny) + f(n + 5, targ, deny) + f(n * 3, targ, deny)

n18 = f(2, 18) * f(18, 49)
n30 = f(2, 30) * f(30, 49)
n1830 = f(2, 18) * f(18, 30) * f(30, 49)

print(n18 + n30 - n1830)