Как это было в демоверсии 2027
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Поменяй местами
Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 100 результатом является число 141?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.
Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 15
Решение и ответ
Обе команды только увеличивают число (В меняет местами цифры, когда десятки меньше единиц, — число растёт). Значит, считаем пути от 100 к 141 рекурсией: из идём в и, если можно, в число с переставленными двумя последними цифрами.
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