Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Need Help For Sprague-Grundy Number

Revision en1, by Foysal_Ahmmed, 2018-02-11 21:08:33

I have just started to learn Sprague-Grundy Number. Now trying to solve lightoj 1296 — Again Stone Game this problem.

Alice and Bob are playing a stone game. Initially there are n piles of stones and each pile contains some stone range[1,10^9]. Alice start the game and they alternate moves. In each move, a player has to select any pile and should remove at least one and no more than half stones from that pile. Who will win the game.

I think it's not possible to solve by Dynamic Programming. Need to find out a pattern. I just calculate some values Sprague-Grundy Number and find a pattern for even number that each even number Sprague-Grundy Number is its own half. (I using term SGN as Sprague-Grundy Number). Like it – SGN(2) = 1, SGN(4) = 2, SGN(6) = 3, SGN(8) = 4.........

For some odd numbers it SGN(1)=0, SGN(3)=0, SGN(5)=1, SGN(7)=0,SGN(9)=2......... But I could not find out any pattern for odd numbers. I can not understand that my observations is right or wrong. Looking help for odd values pattern or a new hints to solve this problem.

Thanks in advance………………………….

Tags game theory, sprague-grundy


  Rev. Lang. By When Δ Comment
en1 English Foysal_Ahmmed 2018-02-11 21:08:33 1194 Initial revision (published)