Розбір
Автор задачі: | Антон Ципко |
Задачу підготував: | Антон Ципко |
Розбір написав: | Антон Ципко |
Блоки 1 та 4
Якщо сума усіх чисел парна, то можемо усі монетки перемістити в одну клітинку, наприклад, .
Блок 5
Можемо знайти найменше непарне число, після чого перемістити усі монетки, крім тієї купки, в одну.
Нехай координати цієї купки такі, що та . Тоді ми можемо кожну купку зсунути або ліворуч (тобто зменшити ), або угорі (тобто зменшити ). Ми це не можемо зробити лише для . Проте там усі наші монетки і залишаться.
Якщо ж або , то ми можемо схожим методом перемістити усі монетки у .
Блок 6
Якщо кількість монеток парна, то застосовуємо алгоритм блоку , інакше — алгоритм блоку .
Блоки 2 та 3
Якщо парне, то застосовуємо алгоритм блоку . Інакше для кожної позиції ми знаходимо відповідь, якби ми зсунули усі монетки ліворуч у позицію , а усі праворуч — у . Серед усіх можливих відповідей — знаходимо найкращу.
Тут потрібно звернути увагу, що якщо з певної сторони виходить непарне число, то його не можна додавати до відповіді.