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

Начало: 2. Цель: 19.
Команды: 1 — n + 1; 2 — n + 2; 3 — n · 3.
Обязательные числа: 9.
Запрещённые числа: 12.

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

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

Этап 1: 2 → 9.
F(2) = 1.
F(3) = F(2) = 1.
F(4) = F(2) + F(3) = 1 + 1 = 2.
F(5) = F(3) + F(4) = 1 + 2 = 3.
F(6) = F(2) + F(4) + F(5) = 1 + 2 + 3 = 6.
F(7) = F(5) + F(6) = 3 + 6 = 9.
F(8) = F(6) + F(7) = 6 + 9 = 15.
F(9) = F(3) + F(7) + F(8) = 1 + 9 + 15 = 25.

Этап 2: 9 → 19.
G(9) = 1.
G(10) = G(9) = 1.
G(11) = G(9) + G(10) = 1 + 1 = 2.
G(12) = 0.
G(13) = G(11) = 2.
G(14) = G(13) = 2.
G(15) = G(13) + G(14) = 2 + 2 = 4.
G(16) = G(14) + G(15) = 2 + 4 = 6.
G(17) = G(15) + G(16) = 4 + 6 = 10.
G(18) = G(16) + G(17) = 6 + 10 = 16.
G(19) = G(17) + G(18) = 10 + 16 = 26.

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

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

Ответ: 650.