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

Начало: 111. Цель: 165.
Команды: A — n + 1; B — s(n).
Обязательные числа: нет.
Запрещённые числа: нет.
Команда B разрешена только при меньшей цифре десятков, чем цифра единиц. Если эти цифры a и b, то после перестановки число возрастает на 9(b − a), то есть строго увеличивается. При равных цифрах команда запрещена; дополнительного способа остаться на месте нет.

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

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

Этап 1: 111 → 165.
F(111) = 1.
F(112) = F(111) = 1.
F(113) = F(112) = 1.
F(114) = F(113) = 1.
F(115) = F(114) = 1.
F(116) = F(115) = 1.
F(117) = F(116) = 1.
F(118) = F(117) = 1.
F(119) = F(118) = 1.
F(120) = F(119) = 1.
F(121) = F(112) + F(120) = 1 + 1 = 2.
F(122) = F(121) = 2.
F(123) = F(122) = 2.
F(124) = F(123) = 2.
F(125) = F(124) = 2.
F(126) = F(125) = 2.
F(127) = F(126) = 2.
F(128) = F(127) = 2.
F(129) = F(128) = 2.
F(130) = F(129) = 2.
F(131) = F(113) + F(130) = 1 + 2 = 3.
F(132) = F(123) + F(131) = 2 + 3 = 5.
F(133) = F(132) = 5.
F(134) = F(133) = 5.
F(135) = F(134) = 5.
F(136) = F(135) = 5.
F(137) = F(136) = 5.
F(138) = F(137) = 5.
F(139) = F(138) = 5.
F(140) = F(139) = 5.
F(141) = F(114) + F(140) = 1 + 5 = 6.
F(142) = F(124) + F(141) = 2 + 6 = 8.
F(143) = F(134) + F(142) = 5 + 8 = 13.
F(144) = F(143) = 13.
F(145) = F(144) = 13.
F(146) = F(145) = 13.
F(147) = F(146) = 13.
F(148) = F(147) = 13.
F(149) = F(148) = 13.
F(150) = F(149) = 13.
F(151) = F(115) + F(150) = 1 + 13 = 14.
F(152) = F(125) + F(151) = 2 + 14 = 16.
F(153) = F(135) + F(152) = 5 + 16 = 21.
F(154) = F(145) + F(153) = 13 + 21 = 34.
F(155) = F(154) = 34.
F(156) = F(155) = 34.
F(157) = F(156) = 34.
F(158) = F(157) = 34.
F(159) = F(158) = 34.
F(160) = F(159) = 34.
F(161) = F(116) + F(160) = 1 + 34 = 35.
F(162) = F(126) + F(161) = 2 + 35 = 37.
F(163) = F(136) + F(162) = 5 + 37 = 42.
F(164) = F(146) + F(163) = 13 + 42 = 55.
F(165) = F(156) + F(164) = 34 + 55 = 89.

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

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

Ответ: 89.