Игра с переворотом двух последовательных положительных результатов на негативы

Question

Мне задавали эти вопросы в одном из моих интервью. Вопросы следующие:

У вас есть строка '+' и '-' (например, ++ ---- ++++++ - + - +). Есть два игрока: Игрок 1 и Игрок 2. При каждом повороте один из игроков может выбрать любые два последовательных '+' i.e. ++ и перевернуть их в. Итак, если исходная строка - ++ ---- ++++++ - + - +, а затем у игрока есть следующие 6 вариантов (2 - 7). (Первый для справки).

1. ++ ---- ++++++ - ++
2. ------ ++++++ - ++
3. ++ - ---- ++++ - + - +
4. ++ ---- + - +++ - + - +
5. ++ ---- ++ - ++ - + - +
6. ++ ---- ++++ - ++
7. ++ ---- ++++ --- ++

игрок происходит поочередно. Игрок, который играет последний ход, победит (или проиграет - не имеет значения).

Учитывая начальную строку, и если игрок 1 принимает первый ход, мы должны сказать, кто победит?

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

Любые идеи о том, как я могу подойти к этому, чтобы решить?

PS - Заинтересованы в подходе, чем в решении. Я прочитал http://www.codechef.com/wiki/tutorial-game-theory, но не смог применить эту же логику здесь.

Answer 1

Здесь мы можем использовать функцию Grundy, потому что после преобразования ++ в - игра делится на сумму из двух отдельных игр: слева от - и вправо. Предположим, что g (l, r) - значение функции Grundy для интервала [l, r] данной строки. Чтобы вычислить его, мы можем попытаться изменить ++ на - во всех возможных позициях, сохранить все g (l, k - 1) xor g (k + 2, r) (где k - позиция, в которой начинается ++) и выберите наименьшее неотрицательное целое число, которое не входит в их число. Значение базового футляра (когда нет возможных ходов) равно 0 или 1 (в зависимости от того, проигрывает или проигрывает последний игрок). Первый игрок выигрывает тогда и только тогда, когда g (0, n - 1) (n - длина входной строки) отлична от нуля. Это решение имеет сложную временную сложность O (n^3) (существует O (n^2) возможных (l, r) пар, и мы можем вычислить ответ в линейном времени для каждого из них).