You have a weighing scale and N weights. Initially both sides of the scale are empty and you have all the N weights in hand. You start by taking a weight randomly and putting it on one side of the scale. You repeat the following procedure until all the weights go to one of the sides of the scale. After each step, you write 'L' if the left side of the scale is heavier and 'R' otherwise. Note that we write R even if the weights of both sides of the scale are equal.
After the procedure, you will have written a string of length N containing 'L' and 'R'. Now, given this output string and value of each of the weight, can you reconstruct the moves made to achieve this particular string?
Warn: 本題有 specialjudge
First line of the input file contains number of test cases, T. This is followed by the description of T test cases. Each test case description starts with integer N, number of weights. Then next line contains N weights w0, w1, wn separated by single space. Next line contains a string of length N, consisting of only 'L' and 'R', which is the output string of the process.
-> number of test cases, T <= 25.
-> number of weights, 1 <= N <= 10000.
-> All weights are positive and less than 1,000,000,000.
-> No two weights are of equal value.
For each test case you will have to output N moves, one per line. For each move print the 0 based index of the weight and the side of the scale you will put this weight in. Output of different test cases is separated by a blank line. There is no blank line after the output of final test case. Please check the sample output for details.
Note
If there are multiple move sequences possible for the given output string, you can output any one of them.
2 2 1 3 LR 2 2 1 LL
0 Left 1 Right 0 Left 1 Left
Migrated from old NTUJ.
CodeCraft 2010
| No. | Testdata Range | Score |
|---|