#algorithm
#алгоритм
Вопрос:
Не мог бы кто-нибудь, пожалуйста, объяснить решение этой проблемы, вы можете проверить проблему здесь: http://community.topcoder.com/stat?c=problem_statementamp;pm=13204 и решение здесь: http://apps.topcoder.com/wiki/display/tc/SRM 624
Я на самом деле не понимаю, как вычисление nimbers и выбор минимального исключенного порядкового номера привели к решению.
Комментарии:
1. Решение, на которое вы ссылались, требует входа в TopCoder. Всегда лучше вкладывать как можно больше контекста в сам пост.
Ответ №1:
Я много боролся с этой проблемой, я пытался решить ее самостоятельно после завершения SRM, но не смог найти решение, поэтому решил прочитать редакционную статью.
Игра, представленная в задаче, является беспристрастной игрой, использующей обычное игровое соглашение, поэтому, основываясь на теореме Спрэга-Гранди, она эквивалентна игре Nim, в которой каждое состояние может быть представлено nimber.
Игра Nim была решена, даже комбинированная игра Nim, состоящая из нескольких отдельных куч Nim, была решена, поэтому есть способ выяснить, у кого из игроков выигрышная стратегия в играх этого типа. Это определяется с помощью nimbers, которые представляют состояния игры. Если перемещение с текущей позиции невозможно, позиция получает nimber 0. В противном случае, согласно теореме Спрэга-Гранди, нимбер позиции — это минимальное неотрицательное целое число, которое не появляется в наборе нимберов, которые могут быть достигнуты за один ход с текущей позиции.
Эта статья очень помогла мне в понимании теории nimber: http://web.mit.edu/sp.268/www/nim.pdf . Что касается доказательства теоремы Спрэга-Гранди, я нашел доказательство из Википедии более понятным.
Комментарии:
1. PDF был очень полезен для понимания концепций nim. Спасибо!