Задание №13. Подсчёт программ: обязательные и запрещённые числа
Подсчёт последовательностей команд по промежуточным числам: сложение вариантов, обязательные участки и ограничения траектории.
Числовой исполнитель получает начальное число и изменяет его разрешёнными командами. Требуется посчитать программы, которые приводят к заданному результату, иногда проходя через обязательные числа и избегая запрещённых. Перечисление всех программ быстро разрастается. Вместо этого для каждого промежуточного числа сохраняется количество способов его получить.
Что именно считается
Программа — последовательность команд. Траектория — последовательность полученных чисел. Например, команды «прибавить 1», затем «прибавить 3» из числа 16 дают результаты 17 и 20. Обратный порядок команд даёт 19 и 20. Конечное число одинаково, но программы разные.
Переходы удобно представить как схему: числа являются её точками, а разрешённые команды — стрелками. Такая схема называется графом. Считать нужно пути с учётом команд на стрелках, а не количество точек схемы. Когда несколько разных команд дают одинаковый результат, каждая из них остаётся отдельным вариантом.
Полный пример: через 16, без 12
В задании EGE-23-0002 ↗ разрешены три команды: прибавить 1, прибавить 3, умножить на 3. Из числа 2 нужно получить 20. Траектория обязательно содержит 16 и не содержит 12.
1. Разделение на участки
Все три команды строго увеличивают положительное число. Поэтому после 16 возврат к меньшему числу невозможен, а через само 16 каждая подходящая программа проходит ровно один раз. Она однозначно делится на два участка:
2\longrightarrow16\longrightarrow20.
Любую допустимую программу первого участка можно продолжить любой программой второго. Если до 16 есть 60 способов, а от 16 до 20 — 3, всего будет 60\cdot3 комбинаций. Эти количества пока требуется вычислить. Запрет 12 действует на всю программу; во втором участке он уже недостижим из-за возрастания.
2. Начало таблицы
Обозначим через F(n) число программ из 2 в число n без посещения 12. Для начала таблицы принимается F(2)=1: есть один способ начать в числе 2, ещё не выполнив ни одной команды. Эта единица нужна, чтобы учесть программы, первая команда которых сразу ведёт из старта в следующее число.
Для чисел меньше 2 значение равно нулю: увеличивающие команды туда не приводят. Запрещённому числу назначается F(12)=0. Это не утверждение, что 12 вообще нельзя получить; в подсчёте исключаются все программы, которые его получают.
3. Подсчёт по последней команде
В число n последняя команда приходит из n-1, из n-3 либо из n/3, если n делится на 3. Эти группы различаются последней командой, поэтому их количества складываются. Сначала находятся два вклада от прибавлений: F(n-1)+F(n-3). При делимости n на 3 к ним добавляется F(n/3). Для начального и запрещённого чисел сохраняются отдельно заданные значения.
Поскольку все предшественники меньше текущего числа, таблица заполняется по возрастанию. Например, до 5 есть два пути: три прибавления единицы или одно прибавление тройки. Поэтому F(5)=2. Для 6 добавляется вариант последнего умножения из 2:
F(6)=F(5)+F(3)+F(2), то есть 2+1+1=4.
| Число n | Программ F(n) |
|---|---|
| 2 | 1 — начальное значение |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 4 |
| 7 | 5 |
| 8 | 7 |
| 9 | 12 |
| 10 | 17 |
| 11 | 24 |
| 12 | 0 — запрет |
| 13 | 17 |
| 14 | 41 |
| 15 | 43 |
| 16 | 60 |
После запрета подсчёт продолжается. В 13 нельзя прийти из 12, но можно из 10 командой прибавления тройки: F(13)=F(12)+F(10), то есть 0+17=17. Запрет посещать 12 не запрещает перепрыгнуть через него.
Для 15 учитывается и умножение из 5: F(15)=41+0+2=43. Число 16 не делится на 3, поэтому F(16)=F(15)+F(13), то есть 43+17=60. Первый участок допускает 60 программ.
4. Продолжения после 16
Умножение на 3 уже приводит как минимум к 48. Вернуться к 20 нельзя, поэтому остаются только прибавления. До цели нужно увеличить число на 4. Это возможно тремя последовательностями:
| Команды | Результаты после команд |
|---|---|
| +1,+1,+1,+1 | 17,18,19,20 |
| +1,+3 | 17,20 |
| +3,+1 | 19,20 |
Двух прибавлений тройки уже слишком много, других команд нет. Значит, продолжений ровно три, а ответ равен 60\cdot3=180.
Проверка подсчёта программой
Тот же пример можно проверить с другого конца: функция f(x) считает продолжения из текущего числа до конца участка. В запрещённом числе или после превышения цели возвращается ноль. В самой цели возвращается единица: один способ закончить участок без дополнительных команд. В остальных случаях складываются продолжения после трёх возможных первых команд.
Кэш убирает повторные вычисления. Он создаётся заново для каждого участка, поскольку цель меняется. Код относится к конкретным возрастающим командам этого примера.
from functools import cache
def count(start, end):
@cache
def f(x):
if x == 12 or x > end:
return 0
if x == end:
return 1
return (
f(x + 1)
+ f(x + 3)
+ f(x * 3)
)
return f(start)
left = count(2, 16)
right = count(16, 20)
total = left * right
print(left, right, total)Вывод: 60 3 180. Проверка совпала с таблицей и отдельным перечислением трёх продолжений.
Как изменяется решение при других условиях
Убывающие команды
В EGE-23-0010 ↗ разрешены вычитание единицы и целая часть деления на 2; требуется путь от 32 до 1 через 10. Числа строго уменьшаются, поэтому участки идут в порядке 32\to10\to1. При прямом заполнении таблицы значения обрабатываются по убыванию. При рекурсивном подсчёте продолжений отсекаются значения меньше цели участка.
Деление выполняется с округлением вниз: 9\mathbin{//}2=4. В частности, последовательность 10\to9\to4\to2 допустима. Подсчёт по двум командам даёт 14 программ до 10 и 30 после него, итого 14\cdot30=420. При наличии нескольких запретов ноль назначается каждому: в EGE-23-0003 ↗ исключаются и 13, и 14.
Два обязательных числа
В EGE-23-0017 ↗ путь от 4 до 15 должен содержать оба числа 11 и 13. Команды увеличивают число, поэтому их порядок определён: 4\to11\to13\to15. Для трёх участков получаются 25, 2 и 2 программы, а произведение равно 25\cdot2\cdot2=100. Сумма случаев «через 11» и «через 13» учитывала бы программы, пропускающие одно из обязательных чисел.
Преобразование цифр
В EGE-23-0080 ↗ одна команда прибавляет единицу, другая увеличивает старшую цифру. На участке от 15 до 36 вторая команда равна прибавлению 10: например, 23\to33. Поэтому применим подсчёт с переходами x+1 и x+10; результат — 16 программ. Оговорка о неизменности числа со старшей цифрой 9 здесь не срабатывает, но в другом диапазоне потребовала бы отдельного анализа.
В EGE-13-0026 ↗ можно прибавить единицу либо поменять местами две младшие цифры, только если десятки меньше единиц. Из 111 обмен запрещён; из 112 получается 121. Сотни сохраняются. Если десятки обозначить t, а единицы — u, изменение при обмене равно 9(u-t)>0. Значит, разрешённые команды возрастают и таблица заполняется по возрастанию; от 111 до 165 получается 89 программ.
Возможные ловушки
- Ноль в начале таблицы. Он обнулит все последующие количества. В EGE-23-0002 ↗ начальная единица обозначает пустой участок до числа 2 и не пересчитывается общей формулой.
- Объединение одинаковых результатов команд. В EGE-23-0022 ↗ из 2 умножение на 2 и возведение в квадрат оба дают 4. Это две команды; замена списка переходов множеством потеряет одну группу программ. Правильный подсчёт с запретом 11 даёт 37.
- Отсечение по неверной стороне. В EGE-23-0010 ↗ значения выше цели нужны для дальнейшего уменьшения. Отсекаются только те, что уже ниже цели участка.
- Обмен цифр без условия. В EGE-13-0026 ↗ произвольный обмен добавит обратные переходы и повторения. Сначала проверяется неравенство цифр, затем выполняется разрешённая команда.
Когда требуется другой подсчёт
В старых задачах встречаются поиск одной программы длиной «не более» заданного числа команд и число различных результатов после «ровно» заданного числа команд. Это другие вопросы. В первом случае сохраняется подходящая последовательность команд; во втором — множество результатов после каждого шага. При движениях в обе стороны состояние включает число уже выполненных команд, а отрицательные значения сохраняются, если они разрешены. Правило отсечения по цели из монотонного примера сюда автоматически не переносится.