Golden Field (Editorial)

Блоки 1 та 4

Якщо сума усіх чисел парна, то можемо усі монетки перемістити в одну клітинку, наприклад, $(1,1)$.

Блок 5

Можемо знайти найменше непарне число, після чого перемістити усі монетки, крім тієї купки, в одну.

Нехай координати $(x,y)$ цієї купки такі, що x>1 та y>1. Тоді ми можемо кожну купку зсунути або ліворуч (тобто зменшити $y$), або угорі (тобто зменшити $x$). Ми це не можемо зробити лише для $(1,1)$. Проте там усі наші монетки і залишаться.

Якщо ж x=1 або y=1, то ми можемо схожим методом перемістити усі монетки у $(n,m)$.

Блок 6

Якщо кількість монеток парна, то застосовуємо алгоритм блоку $4$, інакше — алгоритм блоку $5$.

Блоки 2 та 3

Якщо $m$ парне, то застосовуємо алгоритм блоку $1$. Інакше для кожної позиції $y$ ми знаходимо відповідь, якби ми зсунули усі монетки ліворуч у позицію (1, y-1), а усі праворуч — у (1, y+1). Серед усіх можливих відповідей — знаходимо найкращу.

Тут потрібно звернути увагу, що якщо з певної сторони виходить непарне число, то його не можна додавати до відповіді.