2310.py

"""
Исполнитель Тройник имеет три команды:

    Прибавить 3.
    Сделать нечётное.
    Следующее, кратное 3.

Команда 1 увеличивает число на экране на 3, команда 2 получает число вида 2*х+1, команда 3 получает число, кратное 3, большее текущего.

Программа для исполнителя — это последовательность команд.

Сколько программ существует таких, что при исходном числе 5 будет получено число 89, при этом траектория вычислений исполнителя пройдет через число 23 и не пройдет через число 50?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 5 траектория будет состоять из чисел 8, 9, 19.
"""

# Проверка по примеру: программа 132, исходное 5
# Команда 1 (+3):              5 + 3 = 8
# Команда 3 (след. кратное 3): ((8 // 3) + 1) * 3 = 9
# Команда 2 (2x+1):            9 * 2 + 1 = 19  →  траектория [8, 9, 19] ✓

# Тип 3: содержит 23 (обязательное) + НЕ содержит 50 (запрещённое)
# Разбиваем путь: 5 → 23 → 89, запрет числа 50 действует на оба отрезка.
# Направление: число растёт → провал при x > y.

from functools import lru_cache

@lru_cache(maxsize=None)
def F(x, y, forbidden):
    if x == y: return 1
    if x > y or x == forbidden: return 0
    cmd3 = ((x // 3) + 1) * 3    # следующее кратное 3, большее x
    return F(x + 3, y, forbidden) + F(x * 2 + 1, y, forbidden) + F(cmd3, y, forbidden)

print(F(5, 23, 50) * F(23, 89, 50))