Гвен отдыхает

Автор задачи: Владислав Власов, разработчик: Егор Юлин

Для определенности будем считать, что на каждом шаге $$$n > m$$$ (Если это не так, то мы можем просто поменять стороны прямоугольника, от этого исход игры не изменится).

Заметим, что перед началом хода Гвен у нас может быть три случая:

  1. $$$n$$$ и $$$m$$$ отличаются более чем на $$$1$$$, т.е. их абсолютная разница превосходит $$$1$$$ или $$$|n - m| > 1$$$. Тогда Гвен в своем ходу будет оптимальнее увеличить сторону $$$m$$$, после чего она получит $$$n$$$ очков. Но после этого компьютеру тоже будет оптимально увеличить сторону $$$m$$$, после чего он так же получит $$$n$$$ очков. Не сложно заметить, что после такого хода разница в очках между Гвен и компьютером не изменилась, но стороны прямоугольника станут равны $$$m + 2$$$ и $$$n$$$.

  2. $$$n$$$ и $$$m$$$ отличаются ровно на $$$1$$$ или $$$|n - w| = 1$$$. Тогда в свой ход Гвен будет оптимальнее увеличить сторону $$$m$$$, после чего она получит $$$n$$$ очков. После этого $$$m + 1 = n$$$ и при любой выбранной стороне компьютер получит $$$n$$$ очков. В таком случае разница в очках также не изменится, а стороны прямоугольника станут равны $$$(m + 1, n + 1)$$$ или $$$(m + 2, n)$$$. Не трудно заметить, что стороны прямоугольника все еще отличаются ровно на $$$1$$$.

  3. $$$n = m$$$. Тогда в свой ход Гвен получит $$$n$$$ очков. А после этого для компьютера оптимальным ходом будет увеличение меньшей стороны, после чего он получит $$$n + 1$$$ очков. Разница в очках при этом увеличится на $$$1$$$ в сторону компьютера, а стороны прямоугольника после этого станут равны $$$n + 1$$$ и $$$m + 1$$$.

Иными словами, всегда выгодно увеличивать меньшую сторону прямоугольника, чтобы получить количество очков, равное большей стороне. Понятно, почему в любой конкретный момент такой ход выгоднее, чем увеличение большей стороны, остается только доказать, что такой ход действительно выгоднее в долгой игре. Для этого рассмотрим любую игру и последний момент, в который кто-то из игроков решил увеличить большую из двух сторон прямоугольника.

  1. После момента, когда стороны прямоугольника сравняются, игра будет идти так же.
  2. А между этими моментами были ходы вида «увеличение меньшей стороны», которых у нас останется столько же, а у противника либо останется столько же, либо станет на один больше. Иными словами, если аккуратно расписать последовательность получаемых каждым игроком очков, разность между очками противника и нашими не уменьшится.

Теперь для полного решения данной задачи можно заметить, что пока разница $$$n$$$ и $$$m$$$ превосходит $$$1$$$, на игру это никак влиять не будет, так как игроки будут получать поровну очков. Поэтому мы увеличим $$$m$$$ до $$$n$$$ или $$$n - 1$$$ в зависимости от четности, на это будет потрачено $$$\left\lfloor \frac{n - m}{2} \right\rfloor$$$ ходов. Если ходы после этого закончились, то будет ничья. Если же у нас после этого остались ходы, то если $$$n - m = 1$$$, то снова будет ничья, а если $$$h = m$$$, то победит компьютер, при этом разница в очках будет равна количеству оставшихся ходов.