Задание 13 ЕГЭ по информатике · A0714E

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

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

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

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

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

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

1. Рассмотрим числа как вершины графа. Из каждой вершины проводим переход по команде A к числу, увеличенному на 1.

2. Переход по команде B добавляем только тогда, когда цифра десятков меньше цифры единиц; при этом две младшие цифры меняются местами.

3. Для каждой достижимой вершины вычисляем число программ, приводящих из 100 в это число. Число способов попасть в вершину равно сумме способов попасть в неё из всех предшествующих вершин.

4. После заполнения таблицы динамического подсчёта для числа 150 получаем количество программ, равное 35.