Этот вопрос мне задали в одном из интервью. Вопросы звучат так
У вас есть строка из «+» и «-» (например, ++ ---- ++++++ - + - +). Есть два игрока - Игрок 1 и Игрок 2. На каждом ходу один из игроков может выбрать любые два последовательных знака «+», то есть ++, и перевернуть их на -. Итак, если исходная строка - ++ ---- ++++++ - + - +, а затем у игрока есть следующие 6 вариантов (2-7) (первый для справки).
- ++----++++++-+--+
- ------++++++-+--+
- ++------++++-+--+
- ++----+--+++-+--+
- ++----++--++-+--+
- ++----+++--+-+--+
- ++----++++---+--+
Игроки ходят по очереди. Игрок, который сделает последний ход, выиграет (или проиграет - не имеет значения).
Учитывая начальную строку и если игрок 1 ходит первым, мы должны сказать, кто победит?
Теперь это похоже на классическую задачу теории игр, когда каждый игрок пытается играть оптимально и на каждом шаге делает ход, который перемещает его в выигрышную позицию.
Любые идеи о том, как я могу подойти к этому, чтобы решить?
PS - Интересует больше подход, чем решение. Я прочитал http://www.codechef.com/wiki/tutorial-game-theory, но здесь нельзя применить ту же логику.
