Блог пользователя Foysal_Ahmmed

Автор Foysal_Ahmmed, история, 6 лет назад, По-английски

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………………………….

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

SGN(N) = 0, If (N+1) Can Be represented as a power of 2 SGN(1) = SGN(3) = SGN(7) = SGN(15) = 0 and so on

Otherwise SGN(N) = x(This is Based on observation without any kind of proof)

https://pastebin.com/xpAS7sXJ

as long as the number is not divisible by 2,keep dividing it by 2(integral division) then do an extra division by 2 after done

Again,I dont know how to prove this Would be glad if someone could provide a proof