2303.py

"""
Исполнитель преобразует число на экране с помощью трёх команд, которым присвоены буквы латинского алфавита:

A. Вычесть 5
B. Сделать кратным трём
C. Поделить на 3

Команда A уменьшает число на экране на 5.
Команда B может быть применена только к числам, не кратным трём, и уменьшает число на экране так, чтобы получилось ближайшее к исходному кратное трём число.
Команда C может быть применена только к числам, кратным трём, и уменьшает число на экране в три раза.

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

Сколько программ преобразуют число 103 в число 24, и при этом их траектория вычислений содержит число 73?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 251 траектория состоит из чисел 246, 82, 81.
"""

# Проверка по примеру: программа ACB, исходное 251
# A (–5):              251 - 5 = 246  (246 кратно 3: 246 % 3 == 0)
# C (/ 3):             246 / 3 = 82   (82 не кратно 3: 82 % 3 == 1)
# B (ближайшее ↓ кт.3): 82 - 1 = 81  →  траектория [246, 82, 81] ✓

# Тип 2: траектория ДОЛЖНА содержать 73 (обязательный узел)
# Разбиваем путь: 103 → 73 → 24
# Направление: число уменьшается → провал при x < y.
# Команда B: только если x % 3 != 0; результат x - (x % 3)
# Команда C: только если x % 3 == 0; результат x // 3

from functools import lru_cache

@lru_cache(maxsize=None)
def F(s, end):
    if s == end: return 1
    if s < end:  return 0
    result = F(s - 5, end)                   # A: всегда применима
    if s % 3 != 0:                         # B: только если s не кратно 3
        result += F(s - s % 3, end)
    if s % 3 == 0:                         # C: только если s кратно 3
        result += F(s // 3, end)
    return result

print(F(103, 73) * F(73, 24))