Уиджа

Автор задачи: Александр Голубев, разработчик: Даниил Орешников

Для решения задачи можно было для начала рассмотреть менее общие случаи расположения указателя на доске. Например, если указатель находится в центре доски, то у второго игрока есть симметричная стратегия: всегда после своего хода возвращать его в центр. Аналогично, если указатель находится в середине по одному из направлений, но не по другому, то первый игрок может получить симметричную стратегию, «обрезав» более длинную часть доски, сведя задачу к предыдущему случаю.

Рассмотрев такие случаи, можно было прийти к мысли, что стоит рассматривать не позицию указателя, а количество строк сверху и снизу от него, и количество столбцов слева и справа. Обозначим соответствующие количества за $$$u$$$, $$$d$$$, $$$l$$$ и $$$r$$$ соответственно. Заметим, что за свой ход игрок может просто уменьшить любое из этих чисел на произвольное значение. Говоря формально, наша игра является суммой четырех нимов из $$$u$$$, $$$d$$$, $$$l$$$ и $$$r$$$ камней. Функция Гранди для такой игры принимает значение $$$u \oplus d \oplus l \oplus r$$$, где $$$\oplus$$$ — побитовое исключающее «или».

Выигрышная победа есть у первого игрока тогда и только тогда, когда $$$u \oplus d \oplus l \oplus r \neq 0$$$. Сама выигрышная стратегия заключается в том, чтобы после текущего хода это значение оставалось нулевым. Можно отдельно доказать, что всегда существует ход, приводящий из ненулевого состояния в нулевое, однако это также напрямую следует из свойств функций Гранди. Таким образом, выбирать сторону следовало, опираясь на начальное значение такого выражения, а каждым своим ходом сводить игру к нулевому значению. Чтобы понять, какую сторону следовало резать, можно было проверить существование нулевого состояния для каждой стороны отдельно. Например, чтобы проверить, что существует такое $$$l_1 < l$$$, что $$$u \oplus d \oplus l_1 \oplus r = 0$$$, достаточно было проверить, что $$$u \oplus d \oplus r < l$$$.