0199. The Game (Building a Palindrome)

Input file name:	game.in
Output file name:	game.out
Time limit:	250 ms
Memory limit:	32 megabytes

Two men are playing the following game. The game lasts 2n+1 rounds. In each round players make their moves. The first player chooses a letter (either `A' or `B') which is to be appended to the right end of the current word. Then the second player may swap two letters in the resulting word (which is now one letter longer than before). He can make at most one swap per turn (thus he can do nothing). Initially the word is empty. The second player wins if the final word (the word after the game is over) is a palindrome (palindrome is a sequence of letters which doesn't change after reversion). Your task is to write a program that plays for the second player in the best way (i. e. it gets a palindrome whenever it's possible).

Input file

There are up to five test cases in the input file. In the first line there is a number of games K (1 ≤ K ≤ 5). The following lines contain K test cases. Each test case consists of two lines. The first line of the test case contains an integer number n (0 ≤ n ≤ 127). In the second line there is a sequence of 2n+1 symbols `A' and `B' without spaces, which is the sequence of moves of the first player.

Output file

Write out K groups of lines. The number of lines in the i-th group must be equal to the number of rounds in the i-th game (i. e. in the i-th test case). In the j-th line of the i-th group write out two numbers separated by a single space – the positions of letters which should be swapped by the second player in the j-th round or write out `0 0' if no swap should occur. If the second player can't win, the whole group must consist of lines `-1 -1'.

Your program should work in such way that it only knows first j moves of the first player when choosing a move for j-th round. (i. e. for any two games in which first X moves of the first player match, the first X moves of the second player must also match)

Examples:

game.in	game.out
2 1 BAA 3 AAABAAA	0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Source: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Discuss       Submit a solution



Printable version