РЕШЕНИЕ 23 НОМЕРА (2/3)

Два типа дополнительных условий

В задачах 23 номера часто добавляют ограничения на траекторию вычислений. Есть два основных вида:

1. «Траектория содержит число N» — путь обязательно должен пройти через конкретное число. Решение: перемножаем количество путей от старта до N и от N до финиша.

2. «Траектория не содержит число N» — если в ходе вычислений получается запрещённое число, этот путь считается тупиком. Решение: добавляем проверку в базовый случай.

Шаблон: обязательное число

1
2
3
4
5
6

Логика: путей от start до end через mid = (пути от start до mid) × (пути от mid до end).

Шаблон: запрещённое число

# Траектория НЕ содержит число bad

1
2
3
4
5
6
7

Задача 1. Условие

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

A. Прибавить 2

B. Умножить на 4

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

Разбор

Условие «траектория содержит 200» означает, что путь обязательно проходит через точку 200. Значит, нужно:

1. Найти количество путей от 3 до 200

2. Найти количество путей от 200 до 510

3. Перемножить результаты

Решение

1
2
3
4
5

Ответ: 86

Задача 2. Условие

Исполнитель преобразует число на экране. У исполнителя есть три команды:

A. Вычесть 1

B. Вычесть 3

C. Найти целую часть от деления на 2

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

Решение

1
2
3
4
5
6
7

Ответ: 133