Как решить 13 задание ЕГЭ по информатике 2027?

Условие задания 13 из демоверсии ФИПИ

Источник: проект демоверсии ЕГЭ-2027 по информатике, задание № 13, страница 15. Вот условие целиком:

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

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

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

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.

Как работают две команды

Представим экран с одной кнопкой «+1». Если на экране 100, после одного нажатия появится 101, после двух — 102. Каждый раз, когда в программе встречается буква A, исполнитель нажимает эту кнопку один раз.

Вторая кнопка, B, меняет местами две последние цифры. В числе 101 цифра десятков — 0, а цифра единиц — 1. Ноль меньше единицы, поэтому нажать кнопку можно: 101 → 110. А из 110 вернуться в 101 нельзя: теперь в десятках 1, а в единицах 0. Если цифры равны, как у 111, кнопка тоже недоступна. Обе команды увеличивают число, поэтому возвращаться назад в таблице не придётся.

Пример поменьше: как добраться из 100 до 121

Пока оставим те же две команды, но остановимся на 121. Начнём с вопроса попроще: сколькими способами можно получить 110? Их легко выписать целиком. Первый: десять раз прибавить единицу. Второй: прибавить единицу один раз, получить 101 и поменять цифры местами. Это две разные программы, хотя на экране в конце одно и то же число.

У 111 перестановка ничего дать не может: две последние цифры равны. Зато каждую из двух программ до 110 можно продолжить командой «+1». Так из двух способов получить 110 выходят два способа получить 111. Считаем именно программы: даже если последняя команда у них одна, начало может различаться.

Теперь запишем все числа подряд. Во втором столбце — сколько способов мы уже нашли. В третьем и четвёртом — откуда они пришли. Запись «Из 109: 1» означает, что до 109 дошла одна программа и мы дописали к ней последнюю команду. Тире означает, что такой последней команды быть не могло. У стартового числа 100 ставим 1: мы уже на старте, ни одной команды пока не выполнили.

До 119 включительно после числа 110 в каждой строке остаётся по два способа. Посмотрим, что меняется в строке 120. Два способа приходят из 119 прибавлением единицы. Есть ещё один: дойти до 102 и поменять последние цифры местами. Получается 2 + 1 = 3.

У числа 121 последним шагом могло быть прибавление к 120 — это три программы. Или перестановка цифр в 112 — это ещё две. Итого пять программ. На рисунке выделены три строки таблицы, в которых появляются новые пути. Каждая стрелка показывает, откуда они приходят.

Возвращаемся к условию: сколько программ ведут из 100 в 141

В демоверсии финиш на 20 больше. Продолжим нашу таблицу с того места, где остановились. От 122 до 129 в каждое число можно попасть только прибавлением единицы, так что напротив каждого стоит та же пятёрка, что у 121. Следующая прибавка к числу способов будет в строке 130: туда можно ещё и переставить цифры в 103. Для краткости оставим ниже только строки с таким вторым входом.

Перед последним шагом на экране было либо 140, либо 114. Из 140 прибавлением единицы пришли 14 программ, из 114 перестановкой — ещё две. В бланк ответа идёт 16.

То же решение на Python

Вместо таблицы заведём список ways. Например, ways[110] хранит число программ, которые привели к 110. Вручную мы смотрели, откуда пришли программы. В коде удобнее сделать наоборот: из каждого числа передать накопленный счёт дальше по обеим разрешённым командам.

start, finish = 100, 141
ways = [0] * (finish + 1)
ways[start] = 1

for n in range(start, finish):
    ways[n + 1] += ways[n]          # A: прибавить 1

    tens = (n // 10) % 10
    units = n % 10
    if tens < units:                # B: поменять две цифры
        swapped = (n // 100) * 100 + units * 10 + tens
        if swapped <= finish:
            ways[swapped] += ways[n]

print(ways[finish])

Посмотрим на строку с swapped для числа 112. Выражение (n // 100) * 100 оставляет сотню. Цифра единиц 2 становится десятками, а цифра десятков 1 — единицами. Получается 100 + 20 + 1 = 121. К двум программам, которые попадут в 121 этим путём, позже добавятся три из 120. Поэтому в программе стоит +=: обычное присваивание стёрло бы предыдущий результат.

Программа выводит 16 — ответ из ключа ФИПИ. Для проверки на маленьком примере достаточно в первой строке поставить finish равным 121 вместо 141. Программа выведет 5, как в последней строке нашей первой таблицы.

Если нужен разбор прежней темы номера 13 — адресов и масок подсети, — в проекте ЕГЭ-2027 это уже задание 10: как найти адрес сети по маске.