Задание 13 ЕГЭ: команды, меняющие цифры числа

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

Пример

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

У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 1
B. Поменяй местами

Первая из этих команд уменьшает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению больше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.

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

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

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

Например, для программы ABA при исходном числе 21 траектория состоит из чисел 20, 2, 1.

Решение

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

Заполнив таблицу, получаем для 180 значение 8.

from functools import lru_cache

@lru_cache(None)
def f(x, y):
    if x == y:
        return 1
    if x < y or x == 145:
        return 0
    res = 0
    res += f(x - 1, y)                      # A: вычти 1
    d, e = x // 10 % 10, x % 10             # цифры десятков и единиц
    if x >= 10 and d > e:                   # B применима
        res += f(x - 10 * d - e + 10 * e + d, y)
    return res

print(f(180, 129))

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