As a touring merchant, I come to countries faraway. My wife allows me to travel around only if I return home with a nice, foreign gift in my hands. The game, which was my most recent present to her, was a really fascinating one. The basic rules of the game are fairly simple: The game is played by exactly two players. In front of each player there is a fixed number of mugs and a bowl on the right side of the mugs. The mugs and bowls are arranged in a circle. A number of stones is placed in each mug. The numbers of stones in the bowls are the scores of the corresponding players. The players alternate in making turns. In each turn, the current player selects one of his non-empty mugs. The stones are removed from the selected mug and are spread over the neighbouring mugs and bowls as follows: If there are N stones in the selected mug, one stone is added to each of the following N mugs/bowls in a counter-clockwise direction. Stones in the bowls count as scored points and cannot be removed in any further turn. The following figure shows a turn in the mid of a game: Figure 2 - Board with 3 mugs for each player, scores are 3:4 before the turn and 4:4 after afterwards. If the last stone of a selected mug is added to the own bowl, the player gets an extra move. This extra move may result in additional extra moves (there is no limit for the number of extra moves). If, on the other hand, the last stone is added to a mug of the opponent, the player has the option (not the obligation) to swap the opponent’s mug with his corresponding mug (mugs A and a, mugs B and b, ...). Swapping is only allowed if the own mug is not empty. If he chooses to swap, then both mugs must not be swapped for the following four turns. (Note that this may be different from four moves: Consider the move sequence P0, O1, O2, O3, P4, O5, P6, O7 where Pi is a move by the player and Oj is a move by his opponent, who gets extra moves O2 and O3. If the player swaps mugs in move P0, these two mugs may not be swapped again in moves O1 to P6, but again in O7 and later moves.) Each player may choose the option to swap mugs up to three times within a game. If the last stone is added to a mug of the current player, and if that mug was empty before distri- bution, and if the opposite mug of the opponent is not empty afterwards, the stones from both mugs are captured and put into the current player’s bowl. This rule does not result in an extra move. Note that in general the opposite mug is different from the corresponding mug: Mugs A and c, mugs B and b, and mugs C and a are considered as opposite mugs in the above example. The game ends as soon as every mug is empty and all stones are in the two bowls. If a player cannot move because all of his mugs are empty, but the opponent can move, it is the opponent’s turn again. (With respect to the swapping rule above, the inactivity of the player who cannot move does count as a turn, too.) Otherwise, if a player can move, he has to choose one of the allowed moves.
2/2 Can you help me with the following question: What is the best difference between my final score and my opponent’s final score that I can achieve from a given situation? In addition to me, my opponent also plays optimally. Input The first line gives the number of test cases T (0 < T < 60). Each test case is given in two lines. The first line of a test case holds the number of mugs M for each player (0 < M < 5). The second lines consists of (M + 1) · 2 numbers, describing the current board after your previous turn. The first M numbers describe the number of stones in my mugs in counter-clockwise order. The next number is my score (the stones in my bowl). Then follows the same for my opponent. You may assume that in total there are not more than 15 stones on the whole board. Output For each test case, print one line that gives the best difference between my score and the opponent’s score at the end of the game. At first, it is the opponent’s turn. Sample Input 8 2 000200 2 200000 2 240243 2 200321 3 12130121 4 1210012100 4 9300000003 3 43132100 Sample Output -2 2 -9 -4 5 0 1 -2