Игра

climbit
Эм, вообще-то у вас получилась циклическая динамика: из состояния можно прийти в себя же. Поэтому метод динамического программирования здесь не работает.

BVI94
Для решения избавимся от цикличности в игре. Переформулируя условие, за один ход каждый игрок может либо уменьшить расстояние между фишками (не более чем на K), либо увеличить его (не более чем на K, и не выходя при этом за пределы поля). Таким образом, мы получили игру, похожую на ним с увеличениями. Применяя аналогичные рассуждения, мы получаем, что делать ходы, увеличивающие расстояние между фишками, невыгодно, поэтому их можно не рассматривать.

Таким образом, мы получаем такую игру: есть кучка из N-2 камней (именно таково расстояние между клетками 1 и N), за один ход игрок может взять от 1 до K камней, и кто не может сделать ход - проигрывает. Такая игра решается простой динамикой за O (N * K), однако её решение можно получить и сразу, заметив, что эта игра - фактически k-ним, и ответ определяется просто остатком от деления на K+1.

Еще один вопрос. Есть n кучек по ai камней.
- За один ход разрешается брать камни только с одной кучки.
- Можно брать количество камней, которая является точным квадратом целого числа.
- За один ход нужно взять как минимум один камень

Что делать с этим "квадратом целого числа", какое будет решение?

Прикольная игра.