Problem : 281 - Balls

Special Judge

Problem Statistics

Solved Member: 19　　Submission: 58　　User Tried: 19

Statement:

瀚瀚有一個很長很長的塑膠桶，塑膠桶的左端以及右端有一個開口。

另外，瀚瀚有 n 個球排成序列，球有紅、綠、藍三種顏色，他希望將球依序放入塑膠桶，每次他可以選擇從最左邊放進去或者從最右邊放進去。

神奇的事情是，若球放進塑膠桶之後有兩顆連續的且同樣顏色的球，那麼相鄰且顏色相同的球就會消失不見。瀚瀚希望你告訴他一種放法，使得最後桶中所剩下的球數量是最少的。

Input:Output:

輸入的第一行有一個數字 n ，代表總共有幾顆球。
第二行有長度 n 的字串，依序代表瀚瀚要放入桶中的球。字串由三種字元 'R', 'G', 'B' 組成，R代表紅色球，G代表綠色球，B代表的是藍色球。

限制：

n ≤ 200000
30% 的測試資料滿足： n ≤ 15

請輸出一行長度為 n 的字串，由字元 'R' 以及字元 'L' 所組成。'R' 代表這一顆球要從右端放入桶裡，'L' 代表這一顆球要從左端放入桶裡。

若存在多種放法能夠使得剩下的球數量最少，請任意輸出一種放法即可。

Sample Input:Sample Output:

9
RGBGGBGBR

LLRRRRLLR

HINT:

範例輸出解釋：
由左端放入 R：R
由左端放入 G：GR
由右端放入 B：GRB
由右端放入 G：GRBG
由右端放入 G：GRBGG，最右邊兩個消失，變成 GRB
由右端放入 B：GRBB，最右邊兩個消失，變成 GR
由左端放入 G：GGR，最左邊兩個消失，變成 R
由左端放入 B：BR
由右端放入 R：BRR，最右邊兩個消失，變成 B

最後桶內只剩下一顆球，為最少的情況。

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	65536kb
1-1	500ms	65536kb	10
1-2	500ms	65536kb
1-3	500ms	65536kb
1-4	500ms	65536kb
1-5	500ms	65536kb
2-1	500ms	65536kb	10
2-2	500ms	65536kb
2-3	500ms	65536kb
2-4	500ms	65536kb
2-5	500ms	65536kb
3-1	500ms	65536kb	10
3-2	500ms	65536kb
3-3	500ms	65536kb
3-4	500ms	65536kb
3-5	500ms	65536kb
4-1	500ms	65536kb	10
4-2	500ms	65536kb
4-3	500ms	65536kb
4-4	500ms	65536kb
4-5	500ms	65536kb
5-1	500ms	65536kb	10
5-2	500ms	65536kb
5-3	500ms	65536kb
5-4	500ms	65536kb
5-5	500ms	65536kb
6-1	500ms	65536kb	10
6-2	500ms	65536kb
6-3	500ms	65536kb
6-4	500ms	65536kb
6-5	500ms	65536kb
7-1	500ms	65536kb	10
7-2	500ms	65536kb
7-3	500ms	65536kb
7-4	500ms	65536kb
7-5	500ms	65536kb
8-1	500ms	65536kb	10
8-2	500ms	65536kb
8-3	500ms	65536kb
8-4	500ms	65536kb
8-5	500ms	65536kb
9-1	500ms	65536kb	10
9-2	500ms	65536kb
9-3	500ms	65536kb
9-4	500ms	65536kb
9-5	500ms	65536kb
10-1	500ms	65536kb	10
10-2	500ms	65536kb
10-3	500ms	65536kb
10-4	500ms	65536kb
10-5	500ms	65536kb