|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|20 초 (추가 시간 없음)||1024 MB||0||0||0||0.000%|
You have a special balance scale, with two pans (left and right) that are both initially empty. You also have a box of identical 1-gram marbles. There are N of these marbles, and the marbles are numbered from 1 to N.
Your scale is very sensitive, and you know that if the total weight on the left pan and the total weight on the right pan ever differ by strictly more than 1 gram, the scale will break. For example, if at some point there are 4 marbles in one of the pans, there must be either 3, 4, or 5 marbles in the other pan.
Your friend Libra has challenged you to do the following, without breaking the scale at any point:
Can you find a way to do this?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line with an integer N: the number of marbles. Then, there is one more line with N integers A1, A2, ..., AN, which constitute a permutation of the first N natural numbers. The marble numbered Ai must be the i-th marble that you remove in the removal phase.
For each test case, output one line containing
Case #x: y, where
x is the test case number (starting from 1) and
y is a string of N characters. The i-th of these characters (counting starting from 1) should be uppercase
L if the i-th numbered marble should be put on the left pan, or uppercase
R if it should be put on the right pan.
It is guaranteed that at least one answer exists. If there are multiple valid answers, you may output any one of them.
2 4 3 1 2 4 4 1 2 3 4
Case #1: LRRL Case #2: LRLR
In Sample Case #1, we will put marble 1 on the left pan, then put marble 2 on the right pan, then put marble 3 on the right pan, then put marble 4 on the left pan. Notice that the total weights on the left and right pans — (1, 0), (1, 1), (1, 2), and (2, 2) — never differ by more than 1 throughout this process.
Then, we must remove the marbles in the order 3, 1, 2, 4. Again, the total weights on the left and right pans — (2, 1), (1, 1), (1, 0), (0, 0) — never differ by more than 1 at any point. We have succeeded!
Also notice that
RLLR would be a valid answer for this case, per the same reasoning above (but with the two pans swapped).
Notice that the following are examples of invalid answers for this case:
LLRR: breaks the scale when placing marble 2
LRLR: breaks the scale when removing marble 1 (which is the second marble to be removed)
Although there are no samples with odd N (since that is only possible in Test Set 3), here are some examples:
Rwould be acceptable.
2 3 1:
RLLare the only acceptable answers.
RRRwould break the scale during the placement phase.
RLRwould break the scale during the removal phase.