Задача #4352

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

Уровень ЕГЭ

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

Новая

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

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

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

Ответ

191

from functools import lru_cache

@lru_cache(None)
def f(c, e, k):
  if c > e or k > 3: return 0
  if c == e: return 1 if k == 3 else 0
  p = str(c)
  r = f(c + 1, e, k)
  if '1' in p: r += f(int(p.replace('1', '3')), e, k + 1)
  return r
print(f(11, 94, 0))

Номер