Another Nim's Game Variant
Posted
by
Terry Smith
on Stack Overflow
See other posts from Stack Overflow
or by Terry Smith
Published on 2013-11-03T09:50:45Z
Indexed on
2013/11/03
9:53 UTC
Read the original article
Hit count: 228
algorithm
Given N binary sequence
Example : given one sequence 101001 means
player 0 can only choose a position with 0 element and cut the sequence from that position {1,101,1010} player 1 can only choose a position with 1 element ans cut the sequence from that position {null,10,101000}
now player 0 and player 1 take turn cutting the sequence, on each turn they can cut any one non-null sequence, if a player k can't make a move because there's no more k element on any sequence, he lose.
Assume both player play optimally, who will win ?
I tried to solve this problem with grundy but i'm unable to reduce the sequence to a grundy number because it both player don't have the same option to move. Can anyone give me a hint to solve this problem ?
© Stack Overflow or respective owner