Это простая версия задачи. Единственные отличия между двумя версиями заключаются в ограничениях на \(m\) и \(q\). В этой версии \(m=2\) и \(q=1\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Нарек и Цовак были заняты подготовкой этого раунда, поэтому они не успели сделать домашнее задание, и они решили украсть домашнее задание Давида. Их строгая учительница заметила, что у Давида нет домашнего задания, и теперь хочет его наказать. Она наняла других учительниц, чтобы помочь поймать Давида, и теперь \(m\) учительниц вместе преследуют его. К счастью, они находятся в большом классе, поэтому у Давида есть много мест, где можно спрятаться.
Класс можно представить как последовательность клеток, пронумерованных от \(1\) до \(n\), расположенных на прямой.
Изначально все \(m\) учительниц и Давид находятся в различных клетках. Затем они делают ходы. Во время каждого хода:
- Давид перемещается в соседнюю клетку или остается в текущей.
- Затем каждая из \(m\) учительниц одновременно перемещается в соседнюю клетку или остается в текущей.
Процесс продолжается, пока Давид не будет пойман. Давид пойман, если любая из учительниц (возможно, более одной) находится в той же клетке, что и Давид. Все участники видят ходы других, поэтому все действуют оптимально.
Ваша задача — посчитать, сколько ходов потребуется учительницам, чтобы поймать Давида, если они все действуют оптимально.
Оптимальность действий означает, что ученик делает свои ходы так, чтобы максимизировать количество ходов, необходимых учительницам, чтобы поймать его. А учительницы координируются друг с другом, чтобы сделать свои ходы так, чтобы минимизировать количество ходов, необходимых для поимки ученика.
Кроме того, поскольку Нарек и Цовак считают эту задачу простой, они решили задать вам \(q\) запросов о положении Давида. Примечание: это простая версия, и вам дано только один запрос.
Примечание
В первом примере ученик может просто остаться в клетке \(2\). Учительница, изначально находящаяся в клетке \(1\), может добраться до клетки \(2\) за один ход. Поэтому ответ — \(1\).
Во втором примере ученик должен просто остаться в клетке \(1\). Учительница, изначально находящаяся в клетке \(3\), может добраться до клетки \(1\) за два хода. Поэтому ответ — \(2\).