\begin{tutorial}{Game of Annihilation}

{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Михаил Иванов\\
         Разработка: & Михаил Иванов\\
     \end{tabular}
}

Если у обоих игроков поровну фишек, то сразу заключаем, что исход~--- ничья. Допустим, у них не поровну фишек; назовём \emph{убегающим} того игрока, у которого меньше фишек (и все его фишки будем иногда называть убегающими), и \emph{атакующим} того игрока, у которого больше (и его фишки будем называть атакующими). Ясно, что исходом игры будет либо ничья, либо победа атакующего игрока. Основная идея решения заключается в том, что у убегающего есть лишь один шанс на ничью: добиться того, чтобы у него появилась фишка, которая правее всех фишек противника, к моменту начала его хода. Тогда убегающий просто ею сбежит в сторону $+\infty$.

Оказывается, критерий, что убегающий может добиться ничьей, такой. Пусть у убегающего игрока $n$ фишек, у атакующего игрока $m$ фишек, $m > n$. Отсортируем все фишки убегающего игрока по убыванию координаты, пусть их координаты $e_1 \geqslant e_2 \geqslant \ldots \geqslant e_n$, а у атакующего~--- $a_1 \geqslant a_2 \geqslant \ldots \geqslant a_m$. Пусть $E_i = \sum_{j = 1}^i{e_j}$, $A_i = \sum_{j = 1}^i{a_j}$. Критерий таков: если сейчас ход убегающего игрока, он может добиться ничьей, если и только если существует $i$ от $1$ до $n$, для которого $E_i \geqslant 1 + A_i$. Если сейчас ход атакующего, то убегающий может добиться ничьей, если и только если существует $i$ от $1$ до $n$, для которого $E_i \geqslant 2 + A_i$.

Стратегия за убегающего, если по критерию он может добиться ничьей: взять самое маленькое $i$, для которого $E_i \geqslant 1 + A_i$, и подвинуть вправо любую фишку с индексом от $1$ до $i$ (если отсчитывать фишки справа налево). Легко доказать, что если ход не привёл к аннигиляции, то выполнен критерий ничьей для $i$ ($E_i \geqslant 2 + A_i$), а если привёл к аннигиляции, то для $i-1$ ($E_{i-1} \geqslant 2 + A_{i-1}$). Действительно:
\begin{itemize}
    \item если взаимно уничтожились две фишки с индексами, не превосходящими $i$ (из всех атакующих фишек при отсчёте справа налево и из всех убегающих фишек при отсчёте справа налево), то сначала к сумме $E_i$ добавили единицу, а потом из обеих сумм $E_i$ и $A_i$ выкинули равные слагаемые, отчего разность между ними не поменялась, но они стали $E_{i - 1}$ и $A_{i - 1}$ в новой конфигурации;
    \item если взаимно уничтожились убегающая фишка с индексом, не превосходящим $i$, и атакующая фишка с индексом $j > i$, то можно заключить, что $e_i < a_j \leqslant a_i$, что значит, что $E_i - A_i < E_{i - 1} - A_{i - 1}$, поэтому $i$ не было наименьшим индексом, для которого выполнен критерий ничьей.
\end{itemize}
Аналогично, если выполнено $E_i \geqslant 2 + A_i$ для какого-то $i$ и сейчас ход атакующего игрока, то он ничего с этим не поделает: рассмотрим наименьшее $i$, для которого $E_i \geqslant 2 + A_i$, тогда после хода атакующего игрока будет выполнено $E_i' \geqslant 1 + A_i'$, если не произошло аннигиляции (или аннигиляция не затронула правые $i$ фишек убегающего игрока), и $E_{i-1}' \geqslant 1 + A_{i-1}'$, если атакующий игрок аннигилировал одну из правых $i$ убегающих фишек.

Если же по критерию атакующий игрок побеждает, то его стратегия такая: если не существует двух атакующих фишек, между которыми расположена убегающая, то атакующий игрок может как угодно наступать своими фишками налево, пока не погубит все убегающие фишки. В противном случае он должен взять самую правую атакующую фишку, справа от которой есть убегающая фишка, и её-то и подвинуть вправо. Нетрудно понять, что если он ходом не произведёт аннигиляции, то инвариант сохранится, а если произведёт аннигиляцию, и инвариант нарушится, то он и до хода нарушался. Убегающий игрок ничего не сможет сделать во время своего хода, если по критерию атакующий побеждает, доказательство аналогично.

\end{tutorial}
