ЕГЭ · ЗАДАНИЕ 13
Исполнители и количество программ · №31510
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавь 1
B. Поменяй местами
Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.
Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 100 результатом является число 141?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 16
1. Каждая команда увеличивает число
Команда A прибавляет 1. Команда B разрешена, только когда десятки меньше единиц: перестановка прибавляет 9 × (единицы − десятки), то есть тоже увеличивает число. Поэтому возвратов и циклов нет; числа больше 141 можно не рассматривать.
2. Посчитаем пути к каждому числу
ways[n] — количество программ из 100 в n. Начальное значение ways[100] = 1: до начала выполнения существует одна пустая программа. Из каждого числа переносим число путей ко всем разрешённым следующим состояниям.
ways = [0] * 142
ways[100] = 1
for n in range(100, 142):
if n + 1 <= 141:
ways[n + 1] += ways[n]
tens, units = n // 10 % 10, n % 10
if tens < units:
swapped = n // 100 * 100 + units * 10 + tens
if swapped <= 141:
ways[swapped] += ways[n]
print(ways[141]) # 163. Проверим результат
К 109 существует 1 путь, к 110 — 2, к 120 — 3, к 130 — 6, к 140 — 14, к 141 — 16. Нельзя разрешать перестановку при равных цифрах: она оставила бы число неизменным и создала бесконечные повторения.