Маршрут Кузнечика
Исполнитель Кузнечик перемещается по числовой оси и выполняет команды с заданными длинами прыжков. В задачах важно определить, можно ли попасть из одной точки в другую, сколько существует маршрутов и как изменится ответ при запретных точках или дополнительных ограничениях.
Модель движения Кузнечика
Положение Кузнечика задаётся целым числом на числовой оси. Обычно начальная точка обозначается \(0\) или \(a\), а конечная — \(N\) или \(b\). За один ход Кузнечик может прыгнуть вправо на одну из разрешённых длин: например, на \(1\), \(2\) или \(3\) единицы. Прыжки влево либо запрещены условием, либо рассматриваются отдельно.
Маршрут — это последовательность разрешённых прыжков, которая переводит Кузнечика из начальной точки в конечную. Два маршрута считаются различными, если отличаются хотя бы порядком прыжков.
Например, при прыжках на \(1\) и \(2\) путь \(1+2\) отличается от пути \(2+1\), хотя оба дают перемещение на \(3\). Если требуется попасть именно в точку \(N\), сумма длин прыжков должна быть равна \(N-a\).
Точка достижима, если существует хотя бы одна последовательность разрешённых прыжков, сумма которых равна расстоянию от начальной точки до этой точки. Если разрешены прыжки на \(p\) и \(q\), нужно проверить существование неотрицательных целых \(u\) и \(v\), для которых \(up+vq=N-a\).
При нескольких командах нельзя просто проверять делимость на одну длину: одна точка может достигаться комбинацией разных прыжков. Например, при длинах \(4\) и \(6\) точка на расстоянии \(14\) достижима: \(14=4+4+6\).
Подсчёт маршрутов рекурсией
Для подсчёта маршрутов удобно рассуждать о последнем прыжке. Пусть \(F(x)\) — число маршрутов из начальной точки \(0\) в точку \(x\), а разрешённые прыжки имеют длины \(p_1,p_2,\ldots,p_k\). Последний прыжок в точку \(x\) мог начинаться из одной из точек \(x-p_i\).
Если некоторые точки не существуют или запрещены, соответствующее слагаемое не добавляется. Для старта используется базовый случай: в начальной точке есть ровно один пустой маршрут — маршрут, который ещё не сделал ни одного прыжка.
\(F(0)=1\). Это не означает, что Кузнечик уже сделал ход. Единица нужна для подсчёта маршрутов, начинающихся первым прыжком из точки \(0\). Для недостижимой точки значение равно \(0\).
Такой способ связан с рекурсивным алгоритмом: значение для точки вычисляется через значения для меньших точек. В рекурсивной записи особенно важно правильно задать базовый случай, иначе программа может зациклиться или получить неверный ответ.
Кузнечик прыгает на 1 или 2 клетки. Сколько маршрутов ведёт из 0 в 3?
Динамика и запретные точки
Если значение \(F(x)\) вычислять много раз независимо, рекурсивная программа повторяет одни и те же вычисления. Для больших \(N\) применяют динамику для маршрутов Кузнечика: значения хранят в таблице и рассчитывают по порядку от начальной точки к конечной.
- Создать таблицу \(F[0\ldots N]\) и положить \(F[0]=1\).
- Для каждой точки \(x\) слева направо проверить все разрешённые прыжки.
- Добавить \(F[x]\) к значению точки \(x+p_i\), если она не выходит за границу.
- После обработки всех точек получить ответ \(F[N]\).
Запретные точки рассматриваются в задачах с препятствиями на поле Кузнечика. Если точка \(z\) запрещена, Кузнечик не может в неё приземлиться, поэтому \(F[z]=0\). Кроме того, из неё нельзя продолжать движение: её значение не добавляется к следующим точкам.
Если запрещена начальная точка или конечная точка, число допустимых маршрутов равно нулю. Если запрещена промежуточная точка, исключаются только маршруты, проходящие через неё; остальные продолжают учитываться.
Кузнечик стартует в точке \(0\), прыгает на \(1\) или \(2\), должен попасть в \(5\), а точка \(3\) запрещена. Найдём число маршрутов.
Достижимость и ограничения
Задачи на конечную клетку Кузнечика могут спрашивать не число маршрутов, а сам факт достижимости. Для этого достаточно проверить, что значение \(F(N)\) положительно, если подсчёт маршрутов выполнен без переполнения и дополнительных условий.
Иногда условие задаётся не списком прыжков, а командами исполнителя. Сначала разберите команду Кузнечика: выясните, на сколько клеток разрешено перемещаться, можно ли прыгать влево, повторяется ли команда и есть ли ограничения на число ходов.
Если прыжки направлены только вправо, координата после каждого хода увеличивается, поэтому таблицу можно заполнять слева направо. Если разрешены прыжки в обе стороны, такой порядок обычно уже не работает: могут появиться циклы и бесконечное число маршрутов. В этом случае нужно внимательно изучать ограничение на число ходов или множество состояний.
<ul><li>Считать комбинации, но забывать, что порядок прыжков важен.</li><li>Положить \(F(0)=0\) вместо \(F(0)=1\).</li><li>При препятствии убрать только один переход, но оставить ненулевым значение самой запрещённой точки.</li><li>Разрешить прыжок за конечную точку, если условие требует попасть в неё впервые или двигаться только внутри отрезка.</li><li>Путать число маршрутов с числом посещённых точек.</li></ul>
Если спрашивают «можно ли попасть», ищите существование хотя бы одного маршрута. Если спрашивают «сколько способов», вводите \(F(x)\). При препятствиях обнуляйте запрещённые точки. При большом диапазоне используйте таблицу динамики, а не прямое дерево рекурсивных вызовов.
Связь с рекурсивным деревом
При прямой рекурсии один и тот же подрезультат вычисляется многократно. Например, при прыжках на 1 и 2 значение \(F(5)\) обращается к \(F(4)\) и \(F(3)\), а затем снова получает эти же значения из других ветвей. Дерево рекурсивных вызовов наглядно показывает повторы.
Запоминание уже найденных значений называется мемоизацией. По сути, это тот же принцип динамики: каждое состояние решается один раз. Подробнее о подсчёте маршрутов можно читать на странице подсчёт маршрутов Кузнечика.
| Ситуация | Что хранить | Условие ответа |
|---|---|---|
| Только достижимость | 0 или 1 | Значение равно 1 |
| Число маршрутов | F(x) | F(N) |
| Препятствия | F(x), с обнулением | F(N)>0 или точное число |
| Ограничение на число ходов | F(x,k) | Значение состояния конечной точки |
Проверь себя
Главное
- Маршрут задаётся последовательностью прыжков, причём порядок прыжков важен.
- Для подсчёта маршрутов используется переход \(F(x)=\sum F(x-p_i)\) и базовый случай \(F(0)=1\).
- Запретная точка получает значение \(0\) и не передаёт маршруты дальше.
- Точка достижима тогда и только тогда, когда число маршрутов в неё положительно.
- При больших координатах применяйте динамику или мемоизацию, чтобы не вычислять одинаковые состояния повторно.