Полоска с монетками

Условие

Есть клетчатая полоска $1 \times n$, на которой расположены $k$ монет: $i$-ая монета находится в $a_i$-ой клетке. За один ход игрок может взять какую-то монету и подвинуть её влево на произвольное число клеток, но так, чтобы она не вылезла за пределы полоски, запрещается перепрыгивать другие монеты (или даже ставить две монеты в одну клетку). Проигрывает тот, кто не может сделать ход.

Решение

Первым делом добавим фиктивную монетку, стоящую в самой крайней точке.

Можно заметить, что эта игра эквивалента Лесенка, а именно давайте посчитаем расстояние между соседними монетками, будем считать, что расстояние от $i$-ой до $i+1$-й монетки в текущей задачи - количество монет на $i + 1$-ой ступеньке в оригинальной задаче.

Тогда задача сводится к переместить все монетки на первую ступеньку.

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin