Стратегия для вариационной игры Nim — StoneGameStrategist — SRM 309
Я довольно новичок в теории игр и понял только нормальную игру NIM, где вы удаляете камни из куч без условий и последний игрок, который удалит победы. Но потом я столкнулся с хорошей проблемой при чтении Учебник по теории игр на Topcoder. Суть, как показано ниже:
Вы и ваш друг играете в игру, в которой вы по очереди убираете камни из куч. Первоначально каждая куча имеет как минимум столько же камней, сколько и куча слева. Это свойство должно сохраняться на протяжении всей игры. На каждом ходу вы убираете один или несколько камней из одной кучи. Вы и ваш друг чередуетесь до тех пор, пока больше не будет возможности сделать правильный ход. Последний игрок, который сделал ход, выигрывает игру. Обратите внимание, что если вы удалите все камни из кучи, она все равно будет считаться кучей.
Говорят, что вы сделали «выигрышный ход», если после этого хода вы в конечном итоге сможете выиграть независимо от того, что делает ваш друг. Вам дается int [] сваи, представляющие количество камней в каждой куче слева направо. Ваша очередь двигаться. Найдите выигрышный ход и верните его в виде строки, отформатированной как «ПРИНЯТЬ КАМНИ ИЗ КУКЛЫ k» (цитаты только для ясности), где s и k (индекс на основе 0) представляют собой целые числа без ведущих нулей. Если есть несколько выигрышных ходов, выберите тот, который минимизирует s. Если еще есть связь, выберите ту, которая минимизирует k. Если выигрышный ход невозможен, верните строку «ВЫ ЛЮБИТЕ» (цитаты только для ясности).
У удаления камней здесь есть такое условие, что вам нужно поддерживать общий неубывающий порядок, что становится препятствием для меня при разработке логики. Я пытался читать редакционный для этого, но, к сожалению, не смог понять идею, стоящую за этим. Может кто-нибудь объяснить, пожалуйста, решение в более простых терминах?
Решение
Редакция не объясняет, как решить оригинальную игру Nim, а только дает ссылку на страницу Википедии (где решение можно найти).
В редакционной статье просто объясняется, как сопоставить проблему с Topcoder с проблемой обычной игры Nim:
Во-первых, игру можно преобразовать в игру, в которой сваи имеют различие между исходными сваями (поэтому в примере 3 6 6 получается 3 3 0).
Затем порядок свай меняется на противоположный (поэтому пример становится 0 3 3).
Затем ход в этой новой игре превращается в двухэтапный процесс: уберите камни из одной кучи и добавьте их к предыдущей (в этом примере выигрышный ход берет 3 из последней и добавляет их в среднюю кучу, становясь 0 6 0).
Затем, если вы просто посмотрите на нечетные сваи (# 1, # 3, # 5 и т. Д.), Вы получите обычную игру Nim и можете применить к ней документированный алгоритм (так что 0 3 3 совпадает с Ним позиция 0 3).
Данное объяснение этому таково:
Другие решения
Других решений пока нет …