Задание №13. Короткий конспект
Сумма по командам, произведение обязательных участков, запреты и направление подсчёта программ.
Программа — последовательность команд. Одинаковый конечный результат не делает разные программы одинаковыми. Основной метод: для каждого состояния хранится количество способов его получить.
Правила подсчёта
F(n) — число программ от выбранного старта a до числа n с учётом запретов.
| Ситуация | Правило |
|---|---|
| Начало | F(a)=1: один пустой участок |
| Запрет или недостижимое состояние | Количество равно нулю |
| Разные последние команды | Количество программ до их предшественников складывается |
| Обязательная точка | Количество начал умножается на количество продолжений |
| Несколько обязательных точек | Произведение по всем последовательным участкам |
Произведение применимо, когда путь однозначно делится на участки и любой допустимый первый участок сочетается с любым следующим. В строго монотонных задачах обязательные точки проходятся ровно один раз, в порядке изменения числа.
Порядок решения
- Фиксируются начальное число, цель, все команды, обязательные и запрещённые числа. Уточняется, требуется число программ, один пример программы или число разных результатов.
- Проверяется направление: все команды увеличивают число либо все уменьшают. При строгой монотонности возврата к прежнему значению нет.
- Обязательные числа разделяют путь на участки. Каждый запрет учитывается там, где он достижим.
- Для каждого участка задаётся начальная единица и нули в запретных состояниях. Прямая таблица заполняется по возрастанию для увеличивающих команд и по убыванию для уменьшающих.
- Для очередного числа складываются количества по всем допустимым последним командам. Одинаковые результаты разных команд не объединяются.
- Количество программ на полных участках перемножается. Короткий участок можно проверить перечислением всех его программ.
Компактная проверка
Для +1,+3,\times3 вклад в F(n) дают n-1, n-3 и, только при делимости на 3, n/3. Начальное и запрещённые значения этой формулой не переопределяются.
В EGE-23-0002 ↗: 2\to16\to20, число 12 запрещено; проверка участков даёт 60\cdot3=180.
Возможные ловушки
- Пропущенная кратность: в EGE-23-0022 ↗ удвоение и квадрат из 2 дают 4, но считаются отдельно.
- Неверное отсечение: при убывании отбрасываются значения ниже цели, при возрастании — выше. Для смешанных движений это правило не доказано.
- Запрет как преграда: нельзя получить запрещённое число; перескочить через него одной командой можно.
- Программы вместо результатов: при фиксированной длине для числа разных результатов хранится множество. Для числа программ сохраняются количества; число выполненных команд входит в состояние.