Задание EGEINF07D82E: Подсчёт программ исполнителя

Начало: 20. Цель: 3.
Команды: A — n − 1; B — n − 2; C — ⌊n3⌋.
Обязательные числа: нет.
Запрещённые числа: 13, 14.
Скобки ⌊ ⌋ означают целую часть: остаток от деления отбрасывается.

На рассматриваемом промежутке каждая разрешённая команда строго изменяет число: оно убывает. Поэтому возвращений и циклов нет. Если выйти за конечную границу в направлении движения, вернуться к цели уже нельзя.

На каждом этапе считаем число программ из его начального числа в n. Для первого этапа обозначим его F(n), для следующих используем G(n) и H(n), если они нужны. В начальной точке значение равно 1: это пустая программа. Для недостижимого числа, нецелого аргумента и числа вне промежутка этапа значение равно 0. В запрещённой точке также ставим 0: продолжать путь через неё нельзя.
Любая непустая программа заканчивается одной из разрешённых команд. Складываем количества программ для всех её допустимых предшественников. Если разные команды ведут из одного числа в одно и то же число, это разные программы: соответствующее слагаемое учитывается повторно.
Для остальных точек общая формула имеет вид:
F(n) = F(n + 1) + F(n + 2) + F(3n) + F(3n + 1) + F(3n + 2).
Целая часть деления на 3 равна n для исходных чисел 3n, 3n + 1, 3n + 2. Учитываем каждый из этих прообразов. Нулевые слагаемые из-за выхода за промежуток ниже опускаем. Для G и H действует та же формула со своей начальной точкой.

Этап 1: 20 → 3.
F(20) = 1.
F(19) = F(20) = 1.
F(18) = F(20) + F(19) = 1 + 1 = 2.
F(17) = F(19) + F(18) = 1 + 2 = 3.
F(16) = F(18) + F(17) = 2 + 3 = 5.
F(15) = F(17) + F(16) = 3 + 5 = 8.
F(14) = 0.
F(13) = 0.
F(12) = 0.
F(11) = F(12) = 0.
F(10) = F(12) + F(11) = 0 + 0 = 0.
F(9) = F(11) + F(10) = 0 + 0 = 0.
F(8) = F(10) + F(9) = 0 + 0 = 0.
F(7) = F(9) + F(8) = 0 + 0 = 0.
F(6) = F(20) + F(19) + F(18) + F(8) + F(7) = 1 + 1 + 2 + 0 + 0 = 4.
F(5) = F(17) + F(16) + F(15) + F(7) + F(6) = 3 + 5 + 8 + 0 + 4 = 20.
F(4) = F(12) + F(6) + F(5) = 0 + 4 + 20 = 24.
F(3) = F(11) + F(10) + F(9) + F(5) + F(4) = 0 + 0 + 0 + 20 + 24 = 44.

Всего программ: 44.

Проверка. Независимый перебор последовательностей команд начинается с исходного числа и пробует каждую разрешённую команду отдельной ветвью. Ветка прекращается при попадании в запрещённое число или при выходе за цель. При достижении цели учитываем её только после посещения всех обязательных чисел. Такой перебор даёт 44 программ — столько же, сколько поэтапный подсчёт. Все разрешённые последние команды учтены, а недопустимые ветви исключены. Нужное количество записываем одним целым числом.

Ответ: 44.