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)$. Серед усіх можливих відповідей — знаходимо найкращу.

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