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

Начало: 32. Цель: 1.
Команды: 1 — n − 1; 2 — ⌊n2⌋.
Обязательные числа: 12.
Запрещённые числа: нет.
Скобки ⌊ ⌋ означают целую часть: остаток от деления отбрасывается.

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

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

Этап 1: 32 → 12.
F(32) = 1.
F(31) = F(32) = 1.
F(30) = F(31) = 1.
F(29) = F(30) = 1.
F(28) = F(29) = 1.
F(27) = F(28) = 1.
F(26) = F(27) = 1.
F(25) = F(26) = 1.
F(24) = F(25) = 1.
F(23) = F(24) = 1.
F(22) = F(23) = 1.
F(21) = F(22) = 1.
F(20) = F(21) = 1.
F(19) = F(20) = 1.
F(18) = F(19) = 1.
F(17) = F(18) = 1.
F(16) = F(32) + F(17) = 1 + 1 = 2.
F(15) = F(31) + F(30) + F(16) = 1 + 1 + 2 = 4.
F(14) = F(29) + F(28) + F(15) = 1 + 1 + 4 = 6.
F(13) = F(27) + F(26) + F(14) = 1 + 1 + 6 = 8.
F(12) = F(25) + F(24) + F(13) = 1 + 1 + 8 = 10.

Этап 2: 12 → 1.
G(12) = 1.
G(11) = G(12) = 1.
G(10) = G(11) = 1.
G(9) = G(10) = 1.
G(8) = G(9) = 1.
G(7) = G(8) = 1.
G(6) = G(12) + G(7) = 1 + 1 = 2.
G(5) = G(11) + G(10) + G(6) = 1 + 1 + 2 = 4.
G(4) = G(9) + G(8) + G(5) = 1 + 1 + 4 = 6.
G(3) = G(7) + G(6) + G(4) = 1 + 2 + 6 = 9.
G(2) = G(5) + G(4) + G(3) = 4 + 6 + 9 = 19.
G(1) = G(3) + G(2) + G(2) = 9 + 19 + 19 = 47.

Перемножим результаты этапов: 10 · 47 = 470.
Всего программ: 470.

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

Ответ: 470.