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

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

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

Сколько существует программ, для которых при исходном числе 3 результатом является число 25, при этом траектория вычислений содержит число 10 и не содержит 17?

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

Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 17, 19.

1. Так как все команды увеличивают число, любую подходящую программу можно однозначно разделить в точке, где впервые получается число 10.

2. Количество способов получения каждого числа вычисляем рекуррентно: число способов попасть в x равно сумме количеств способов попасть в x−2, x−3 и x/2, если x чётно. При подсчёте программ от 10 до 25 способы, проходящие через 17, не учитываем.

3. Перемножение количества допустимых программ на первом и втором участках даёт общее число программ.

4. После выполнения динамического подсчёта получаем 90 допустимых программ.