Today I was participating in 2012-2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest , We solved 12/13 problems ^_^. The problems were very interesting. :D

The one I couldn't solve was "H — Game with the Stones", even though I had a bit more than 2 hours to think about it, I only got WA on test 16...

I will explain where I got so far and please tell me what I am doing wrong.

at first I came up with this pattern for a single pile: L, W, L, W, W, W, L, W, W, W, L, W, W, W, L...

for every x%4 =  = 1 we can split it to (x - 2, 2) which is a losing position for the opponent.

for every x%4 =  = 3 there is no way to get a winning position no matter how we split it.

for every even x we can split it to (x - 1, 1) or (x - 3, 3) to get the opponent to a losing position x - 1 or x - 3..

so win if X%4! = 3 and lose otherwise...

I then noticed that we only care about the 'longest' pile.. and I found what would be the length of the pile (the number of turns until it gets all 1s)

I found this pattern for the length of a pile: 0, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8 ...

length(x) = x / 2 + (x%4! = 2)

finally I look for the largest winning pile and make sure that all the other piles can be finished before it, meaning that length((a_i + 1) / 2) is less than length(W). (W is the largest winning pile and a_i are all the other piles)

this is my code

anyone have an idea what I am doing wrong here? and/or how to solve this problem?

I always have rough time with game theory problems.. so I am trying to get a better understanding on how to think analyze and come up with the solution...