Задание 13 демоверсии ЕГЭ 2027 по информатике: разбор

Анализ хода исполнения алгоритма. Реши сам, потом открой решение.

Задание 13

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

У исполнителя есть две команды, которые обозначены латинскими буквами:

A. Прибавь 1

B. Поменяй местами

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

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

Сколько существует программ, для которых при исходном числе 100 результатом является число 141?

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

Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.

Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 15

Решение и ответ

Обе команды только увеличивают число (В меняет местами цифры, когда десятки меньше единиц, — число растёт). Значит, считаем пути от 100 к 141 рекурсией: из $x$ идём в $x + 1$ и, если можно, в число с переставленными двумя последними цифрами.

def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0
    k = f(x + 1, y)                      # команда A
    d, e = x // 10 % 10, x % 10
    if d < e:                            # команда B допустима
        k += f(x - 10 * d - e + 10 * e + d, y)
    return k

print(f(100, 141))

Например, 112 → 121 по команде B, 134 → 143 уже перелетает 141 — такие ветки дают 0. Всего путей 16.

Ответ: 16