Simple Game of Sticks

Problem #180

Tags: games puzzle

Who solved this?

This game have been puzzling me for about dozen years. Recently I encountered one of its variation once again - it was given as a part of exam for to-be-interns by some software corporation.

It is played between two participants. They lay several objects (matchsticks, little stones, coins) in a single line. This line can have several spaces, for example:

| | |    | | | |    | |

Here are three groups, containing 3, 4 and 2 sticks. At each move the player can take any 1 or 2 adjacent sticks (it is forbidden to take 2 sticks belonging to different groups). Of course some of the groups can split into smaller one after the move.

The person who is forsed to take the last stick - loses.

For example, the position shown above can evolve as following:

| | |    | | | |    - |         player A took 1 stick from the last group of 2

| | |    | - - |      |         player B took 2 sticks from the middle group of 4 (splitting it)

| - |    |     |      |         player A took 1 stick from the middle of group of 3

After this move there are 5 separated sticks so any further moves would consist of taking a single stick - e.g. player B loses the game.

Obviously for each position it is predetermined whether it is losing or winning if both players keep optimal strategy. For example in this case player B could probably win if after the first move of A he would take 2 sticks from the first group, reducing position to 1 4 1 instead of 3 1 1 1. Is it correct? Can you prove it?

Input data: will provide the number of testcases in the first line.
Next lines will contain a single test-case each - specifying a sequence of groups of (initially) adjacent sticks, e.g. 3 4 2 for the starting position proposed above.
There will be no groups larger than 7 sticks and average quantity of groups will be about 10.
Answer: should contain for each position either 1 if it is winning or 0 otherwise.

Example:

7
1
1 1
1 1 1
4
2 2
3 3
1 4

0 1 0 0 0 0 1

We call position winning if the first person to move can win if playing optimally and losing otherwise.

You need to login to get test data and submit solution.