\begin{tutorial}{Побег от зомби}

\textit{Автор задачи и разработчик: Павел Скобелин}
\vspace{0.2em}

Для каких-то продвижений по задаче нужно было понять более простой способ вычисления функции $f$. 

Покажем, что существует путь минимальной длины до точки $(x, y)$, такой, что он состоит только из ходов длины $1$. 

Несложно показать, что любой ход на $x$, где $x>2$, строго выгоднее заменить на $5$ ходов: $1 + 1 + (x - 2) + 1 + 1$, так как 
$$1^2+1^2+(x-2)^2+1^2+1^2 = x^2 - 4x +4 + 4 = x^2 - 4x + 8 < x^2$$

Далее нужно показать, что можно заменить все отрезки длины $2$, и получить ответ не хуже. Но, на самом деле, это не было необходимо: Даже имея этот факт, несложно показать, что функция $f$ выглядит так: $f(x, y) = 2 \cdot \max(|x|, |y|) - ((x + y) \mod 2)$. Это можно показать по индукции.

Далее, понимая, как выглядит функция, есть несколько решений. Первое решение~--- бинарный поиск. Для начала, нужно добиться такого, чтобы у загаданной точки координата по оси $OX$ совпадала с координатой по оси $OY$. Как такое сделать? Для удобства, первым действием можно было передвинуть точку в первую четверть. После этого заметим, что если мы уменьшим меньшую координату на четное число, то наша функция никак не изменится, а если большую~--- то изменится. Значит, несложно за 1 запрос понять, какая координата больше. Далее, можно было делать бинарный поиск, чтобы понять, в какой момент функция начнет изменяться относительно изначальной позиции. То есть, если $f(x, y) = f(x + 2, y) = \dots = f(x+2k, y) < f(x+2k+2, y) < f(x+2k+4,y)$, значит, что $y \in [x+2k, x+2k+2)$. После этого аккуратным разбором случаев можно было добиться уравнивания координат.

Теперь мы знаем, что $x=y$. Тогда, если мы будем поддерживать инвариант, будет выполняться $f(x, y) = 2 \cdot x$. Значит, нам нужно уменьшать $x$ (и $y$), пока функция расстояния не начнет снова расти. Этот момент нужно найти бинарным поиском~--- несложно показать, что это единственный момент, в который координата  точки будет $(0, 0)$. 

Таким образом, решение работает за 2 бинарных поиска, требующих порядка $32$ запросов, что легко укладывается в ограничения.

\end{tutorial}
