Задание 13 ЕГЭ: арифметические команды

Исполнитель с арифметическими командами: число программ. Тема номера — количество программ исполнителя. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Исполнитель преобразует число на экране.

У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычти 2
B. Вычти 3
C. Найди целую часть от деления на 2

Первая из них уменьшает число на экране на 2, вторая уменьшает его на 3, третья заменяет число на экране на целую часть от деления этого числа на 2.

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

Сколько существует программ, для которых при исходном числе 44 результатом является число 6, и при этом траектория вычислений содержит число 38?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы CAB при исходном числе 57 траектория состоит из чисел 28, 26, 23.

Решение

Все команды только уменьшают число, поэтому программ конечное число, и их удобно считать таблицей от 6 вверх к 44: в клетке 6 — 1, в клетке n — сумма значений в клетках, куда ведут применимые команды (если они не проскакивают 6).

Обязательное число делит путь на независимые участки, их ответы перемножаются. Участки: 44 → 38: 2, 38 → 6: 5617. Ответ: 2 · 5617 = 11234.

from functools import lru_cache

@lru_cache(None)
def f(x, y):
    if x == y:
        return 1
    if x < y:
        return 0
    res = 0
    res += f(x - 2, y)                      # A: вычти 2
    res += f(x - 3, y)                      # B: вычти 3
    res += f(x // 2, y)                     # C: найди целую часть от деления на 2
    return res

print(f(44, 38) * f(38, 6))

Решить такую задачу — новый вариант с проверкой