Исполнитель преобразует число на экране. У исполнителя есть пять команд, которым присвоены номера:
1. Увеличь на разряд единиц
2. Увеличь на разряд десятков
3. Умножь на разряд единиц
4. Умножь на разряд десятков
5. Прибавь 1
Первая и третья команды используют значение разряда единиц числа (например у 13 это 3, а у 28 — 8), а вторая и четвертая команды используют значение разряда десятков числа (например у 81 это 8, а у 35 это 3). Причём не разрешается выполнять команду, если после неё число на экране не изменится, либо превратится в 0. Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 25 результатом является число 111, если известно, что нельзя повторять команду, сделанную два шага назад (например программа 112 допустима, а 121 — нет)?
from functools import lru_cache # c1 - номер команды на предыдущем шаге # с2 - номер команды на ПРЕДпредыдущем шаге @lru_cache(None) def f(a, b, c1 = 0, c2 = 0): if a > b: return 0 if a == b: return 1 s = 0 x = a % 10 # Число единиц y = a // 10 % 10 # Число десятков if c2 != 1 and x != 0: s += f(a + x, b, 1, c1) if c2 != 2 and y != 0: s += f(a + y, b, 2, c1) if c2 != 3 and x != 0 and x != 1: s += f(a * x, b, 3, c1) if c2 != 4 and y != 0 and y != 1: s += f(a * y, b, 4, c1) if c2 != 5: s += f(a + 1, b, 5, c1) return s print(f(25, 111))