Задача #4351

Количество программ

Уровень ЕГЭ

(А. Шуруха) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Прибавь 3
C. Замени цифру
Первая команда увеличивает число на экране на 1. Вторая команда увеличивает число на экране на 3. Третья команда применяется
только к числу, в записи которого присутствует хотя бы одна цифра 1, и действует, заменяя число на экране числом, в котором
каждая цифра 1 заменена на цифру 3.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 11 результатом является число 94, и при этом никакие две
одинаковые команды не идут подряд?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABC при исходном числе 11 траектория состоит из чисел 12, 15, 35.

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

1888

from functools import lru_cache

@lru_cache(None)
def f(c, e, last):
  if c > e: return 0
  if c == e: return 1
  p = str(c)
  r = 0
  if last != 'A': r += f(c + 1, e, 'A')
  if last != 'B': r += f(c + 3, e, 'B')
  if '1' in p and last != 'C': r += f(int(p.replace('1', '3')), e, 'C')
  return r
print(f(11, 94, ''))

Номер