Many Thanks to Clive Fraser for this curious problem!
Charles and Diana were clearing up after a particularly good party. The decorations included a number of paper streamers in a variety of different colours. They seemed too good to throw away. Diana had an idea to create a game which would use the long narrow strips of paper. This was to be a paper cutting game where they would take it in turns to cut one of the strips into two pieces, thereby increasing the number of strips by one. After some discussion they decided on the following rules for the game.
At the start of the game there would be several paper strips of varying lengths. These would not be added to or removed during the course of a
game. During any one turn a player would select one of the strips and cut it into two pieces. The two pieces could be any length provided that
each piece was at least 1 cm long. The two pieces are then returned to the pile of strips in the game (increasing the number of strips by one)
and are then available for future turns. Charles is to be the first player in each game. The game ends when a player cannot make a valid cut in
any of the remaining pieces. The first player who cannot make a move loses the game.
It should be obvious that any strip of paper which is shorter than 2 cm cannot have a valid cut made in it, because it is not possible for
both of the pieces to be at least 1 cm in length. A strip of exactly 2 cm in length has only one valid cut which creates two strips of
length 1 cm. A strip of length 3 cm has an infinite number of valid cuts. It can be cut into a length of 1 cm and another length of 2 cm.
The strip of length 2 cm can then be used for a valid cut later in the game. Another possibility is to cut the strip of length 3 cm into strips
of length 1.64 cm and 1.36 cm. Neither of these can be used for any further valid cuts. A strip of 5 cm can be cut into two strips in such
a way that, either only one of the strips, or both of the strips, are available for further valid cutting.
This game is one of a class of games where the winner is determined by the initial conditions (assuming optimal play). Exactly one of the following two statements must be true for a given set of initial conditions:
You will be given a series of games in their initial setup. For each of these you need to determine which of Charles and Diana will win the game (assuming optimal play). Remember that Charles makes the first move.
The initial setup for each game will consist of a maximum of 10 paper strips. The initial lengths of the strips will be integers and all will
be at least 2 cm. No strip will be longer than 200000 cm. After cutting there is no need for the cut strips to have integral length,
provided that both are at least 1 cm long.
Input/Output description: The first line of the input data will be a single integer N for the number of puzzles to be solved. N lines
will follow. Each line has between 3 and 10 space-separated integers, which are the initial lengths of the paper strips. For each puzzle, use a
single letter (C or D) to indicate the winner. Give all answers, separated by spaces, as a single string.
Example:
input:
4
5 7 8
4 16 18
28 36 37
12 26 33 39
answer:
D D C C