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

Начало: 100. Цель: 143.
Команды: 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: 100 → 143.
F(100) = 1.
F(101) = F(100) = 1.
F(102) = F(101) = 1.
F(103) = F(102) = 1.
F(104) = F(103) = 1.
F(105) = F(104) = 1.
F(106) = F(105) = 1.
F(107) = F(106) = 1.
F(108) = F(107) = 1.
F(109) = F(108) = 1.
F(110) = F(101) + F(109) = 1 + 1 = 2.
F(111) = F(110) = 2.
F(112) = F(111) = 2.
F(113) = F(112) = 2.
F(114) = F(113) = 2.
F(115) = F(114) = 2.
F(116) = F(115) = 2.
F(117) = F(116) = 2.
F(118) = F(117) = 2.
F(119) = F(118) = 2.
F(120) = F(102) + F(119) = 1 + 2 = 3.
F(121) = F(112) + F(120) = 2 + 3 = 5.
F(122) = F(121) = 5.
F(123) = F(122) = 5.
F(124) = F(123) = 5.
F(125) = F(124) = 5.
F(126) = F(125) = 5.
F(127) = F(126) = 5.
F(128) = F(127) = 5.
F(129) = F(128) = 5.
F(130) = F(103) + F(129) = 1 + 5 = 6.
F(131) = F(113) + F(130) = 2 + 6 = 8.
F(132) = F(123) + F(131) = 5 + 8 = 13.
F(133) = F(132) = 13.
F(134) = F(133) = 13.
F(135) = F(134) = 13.
F(136) = F(135) = 13.
F(137) = F(136) = 13.
F(138) = F(137) = 13.
F(139) = F(138) = 13.
F(140) = F(104) + F(139) = 1 + 13 = 14.
F(141) = F(114) + F(140) = 2 + 14 = 16.
F(142) = F(124) + F(141) = 5 + 16 = 21.
F(143) = F(134) + F(142) = 13 + 21 = 34.

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

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

Ответ: 34.