Simple Game of Sticks
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
2 sticks. At each move the player can take any
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.
B loses the game.
Obviously for each position it is predetermined whether it is
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
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
Answer: should contain for each position either
1 if it is
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