This problem was kindly offered by Clive Fraser - many thanks!
Ann and Bob enjoy playing games. One of their favourite games is the Game of Stones. This consists of a line of wooden bowls set out from left to right. Each bowl contains a number (possibly 0) of stones. The players take it in turns to make a move. A move requires a player to remove a stone from any bowl, other than the rightmost bowl, and to place the stone in any bowl which is further to the right than the bowl from which it was removed. The consequence of these moves is that stones always move to the right and that all stones will eventually be in the rightmost bowl. The game ends when all stones are in the rightmost bowl. The first player to have no valid move loses the game. This is equivalent to saying that the player who moves the final stone into the rightmost bowl wins the game.
Suppose that we have a small game with only 4 bowls, with the number of stones in each bowl (from left to
right) being 4, 3, 2 and 1. There are 6 possible moves from this position. The table below shows the
number of stones in each bowl after each of these moves has been played.
3 4 2 1
3 3 3 1
3 3 2 2
4 2 3 1
4 2 2 2
4 3 1 2
Note that removing a stone from the rightmost bowl is not allowed. For this small example it is fairly easy to generate all possible move sequences and to confirm that the first player is certain to win, provided that they play optimally. For any starting position optimal play will guarantee a win either for the first or second player. This means that, before the first player makes a move, the winner of the game is known, provided that both players play optimally. Ann and Bob are very good players so they tend to play optimally at all times. As this would seem to remove any incentive for them to play the game, it is not surprising that they have modified the way in which they play it. Ann always plays the first move but the two players take it in turns to set the initial game arrangement. The person who sets the puzzle always sets up the game so that they will win. Thus the game starts with both players knowing who is going to win. However, the player who set the puzzle has got to play a perfect game in order to win. A single mistake is likely to forfeit the game. So the player who set the puzzle has to concentrate hard to make all of the correct moves. Meanwhile their opponent is continually trying to come up with moves that cause the other player to make a mistake. In this way both players have an enjoyable game.
You will be given a number of puzzles where the person who set them also won the game (as expected). These have been randomised so that alternate puzzles are not set by alternate players. In other words the order of winning players in the sequence of puzzles is quite random. For each puzzle you need to determine which player (Ann or Bob) set the puzzle and won the game.
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 pairs of lines will follow. The first line of the pair is a single integer M, for
the number of bowls in the puzzle. The second line of the pair contains M space-separated integers, giving the
initial number of stones in each bowl (from left to right). For each puzzle use a single letter (A or B) to
indicate the winner. Give all answers, separated by spaces, as a single string.
Example:
input:
2
4
4 3 2 1
8
11 4 3 10 7 6 7 5
answer:
A B