Well, this stuff is a bit complicated, involving a lot of math. With this kind of problems there is an interesting story. I was participant of CEOI 2000, where was very similiar problem (
http://ceoi.ubbcluj.ro/internet/p5.html). This problem can be easily and efficiently solved by Grundy numbers. Participants from my country knew it, because we have trained Grundy numbers on our local contests. Problemsetters probably didn't know this theory, so the sample solution was something like backtrack. That's why we've wondered, why the input is so small, when we can solve quickly a lot larger inputs.
So a rough idea for this problem: Firstly, we check, whether there are two X in a row. Winning moves in such position are clear. So assume, that input looks like this: a_1 dots, X, a_2 dots, X, ... X, a_n dots. We divide this game to n independent games.
First thing to consider is that position: X a_i dots X is the same as position: a_i-4 dots assuming that both players play perfectly. This is because one can't make X in first two or last two dots, because the other player will win easily. (similiar for positions a_i dots, X and X, a_i dots (X only on one of the sides) These are equivalent to a_i-2 dots) So the initial position turns out to be n independent positions with a_1-2, a_2-4 ... ,a_{n-1}-4, a_n-2 dots.
For every position we compute nonnegative integer called Grundy number. Grundy number equals zero iff the position is losing. Grundy number for the position P is the minimum number x such that we can't get from P to position with Grundy number x.
Grundy number of a position, which is a set of independent positions is XOR of grundy numbers of that independent positions.
If we have position with k dots, to which positions we can get? Consider we put X on i-th dot. We will get position: (i-1) dots, X, (k-i) dots. We know that this is equivalent to 2 independent positions: first is (i-3) dots, second is (k-i-2) dots. If g1 is grundy number for first position and g2 is grundy number for second position then grundy number of these 2 indepedent positions is g1 XOR g2. So from position with k-dots, we can get to position with grundy number g1 XOR g2. We compute this for every i and we get grundy numbers of all positions, we can get to. Minimum value not in this list is a grundy number for the position with k-dots.
Position with zero (or less
) dots has grundy number zero. (because it is losing) So now we can compute grundy number for every position with k-dots.
So return to initial position. It is n independent positions with a_1-2, a_2-4 ..., a_n-2 dots. Let G(i) be the grundy number for position with i-dots, then grundy number for initial position is G(a_1-2) XOR G(a_2-4) XOR ... XOR G(a_n-2). If this number is zero, initial position is losing. If is it positive, it is winning position. How to find all winning moves? That's simple, try all possible moves, and the one, that will give the resulting position with grundy number zero is winning move.
Why is it true? Well this is where that 'a lot of math' comes
But don't want me to explain it in this post
