0У
Все задачи №13
№13

+1 и замена цифры 1 на 3

Исполнитель преобразует число на экране. У исполнителя две команды: A. Прибавь 1 B. Измени цифру A увеличивает число на 1. B применяется только к числу, в записи которого есть хотя бы одна цифра 1, и заменяет в нём каждую цифру 1 на цифру 3. Сколько существует программ, для которых при исходном числе 10 результатом является число 84? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 34, 35.

Источник: ФИПИ (Резервная 22.06.2026), № 31229

Ответвпиши то, что вывела программа
Показать разбор
  1. Напиши функцию f(x, end): сколько программ ведёт из x в end.
  2. Если x == end, верни 1. Если x > end, верни 0: команды только увеличивают число.
  3. Собери список moves: команда A есть всегда.
  4. Команду B добавляй, только если в записи числа есть цифра 1. Замени единицы на 3 через replace.
  5. Верни сумму moves и выведи f(10, 84).
def f(x, end):
    if x == end: return 1
    if x > end: return 0
    moves = [f(x + 1, end)]
    if '1' in str(x):
        moves.append(f(int(str(x).replace('1', '3')), end))
    return sum(moves)

print(f(10, 84))