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

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

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

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

Этап 1: 2 → 39.
F(2) = 1.
F(3) = F(2) = 1.
F(4) = F(2) + F(3) = 1 + 1 = 2.
F(5) = F(4) = 2.
F(6) = F(2) + F(3) + F(5) = 1 + 1 + 2 = 4.
F(7) = F(6) = 4.
F(8) = F(4) + F(7) = 2 + 4 = 6.
F(9) = F(3) + F(8) = 1 + 6 = 7.
F(10) = F(5) + F(9) = 2 + 7 = 9.
F(11) = F(10) = 9.
F(12) = F(4) + F(6) + F(11) = 2 + 4 + 9 = 15.
F(13) = F(12) = 15.
F(14) = 0.
F(15) = F(5) = 2.
F(16) = F(8) + F(15) = 6 + 2 = 8.
F(17) = F(16) = 8.
F(18) = F(6) + F(9) + F(17) = 4 + 7 + 8 = 19.
F(19) = F(18) = 19.
F(20) = F(10) + F(19) = 9 + 19 = 28.
F(21) = F(7) + F(20) = 4 + 28 = 32.
F(22) = F(11) + F(21) = 9 + 32 = 41.
F(23) = F(22) = 41.
F(24) = F(8) + F(12) + F(23) = 6 + 15 + 41 = 62.
F(25) = F(24) = 62.
F(26) = F(13) + F(25) = 15 + 62 = 77.
F(27) = F(9) + F(26) = 7 + 77 = 84.
F(28) = F(27) = 84.
F(29) = F(28) = 84.
F(30) = F(10) + F(15) + F(29) = 9 + 2 + 84 = 95.
F(31) = F(30) = 95.
F(32) = F(16) + F(31) = 8 + 95 = 103.
F(33) = F(11) + F(32) = 9 + 103 = 112.
F(34) = F(17) + F(33) = 8 + 112 = 120.
F(35) = F(34) = 120.
F(36) = F(12) + F(18) + F(35) = 15 + 19 + 120 = 154.
F(37) = F(36) = 154.
F(38) = F(19) + F(37) = 19 + 154 = 173.
F(39) = F(13) + F(38) = 15 + 173 = 188.

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

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

Ответ: 188.