Два типа дополнительных условий
В задачах 23 номера часто добавляют ограничения на траекторию вычислений. Есть два основных вида:
1. «Траектория содержит число N» — путь обязательно должен пройти через конкретное число. Решение: перемножаем количество путей от старта до N и от N до финиша.
2. «Траектория не содержит число N» — если в ходе вычислений получается запрещённое число, этот путь считается тупиком. Решение: добавляем проверку в базовый случай.
Шаблон: обязательное число
123456
Логика: путей от start до end через mid = (пути от start до mid) × (пути от mid до end).
Шаблон: запрещённое число
# Траектория НЕ содержит число bad
1234567
Задача 1. Условие
Исполнитель преобразует число на экране. У исполнителя есть две команды:
A. Прибавить 2
B. Умножить на 4
Сколько существует программ, для которых при исходном числе 3 результатом является число 510, при этом траектория вычислений содержит число 200?
Разбор
Условие «траектория содержит 200» означает, что путь обязательно проходит через точку 200. Значит, нужно:
1. Найти количество путей от 3 до 200
2. Найти количество путей от 200 до 510
3. Перемножить результаты
Решение
12345
Ответ: 86
Задача 2. Условие
Исполнитель преобразует число на экране. У исполнителя есть три команды:
A. Вычесть 1
B. Вычесть 3
C. Найти целую часть от деления на 2
Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория не содержит числа 7 и содержит 10?
Решение
1234567
Ответ: 133
