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

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

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

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

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

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

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

1. Обозначим через f(n) количество программ, переводящих число 100 в число n. Из 100 можно начать только командой A, поэтому f(100)=1.

2. Для любого числа n переход по команде A приходит из числа n-1. Дополнительный переход по команде B возможен, если перестановка двух последних цифр числа-источника разрешена.

3. Последовательно подсчитывая значения, получаем: f(112)=2, f(113)=2, f(114)=2; f(120)=3, f(121)=5, f(122)=5, ..., f(129)=5.

4. Далее: f(130)=6, f(131)=8, f(132)=13, f(133)=13, ..., f(139)=13.

5. В число 143 можно попасть командой A из 142 или командой B из 134, поскольку в числе 134 цифра десятков меньше цифры единиц.

6. Следовательно, f(143)=f(142)+f(134)=21+13=34.