2016年2月25日 星期四

[HOJ 281]Balls (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 281 - Balls

Special Judge

Problem Statistics
Solved Member: 19  Submission: 58  User Tried: 19
Problem:
瀚瀚有一個很長很長的塑膠桶,塑膠桶的左端以及右端有一個開口。

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

神奇的事情是,若球放進塑膠桶之後有兩顆連續的且同樣顏色的球,那麼相鄰且顏色相同的球就會消失不見。瀚瀚希望你告訴他一種放法,使得最後桶中所剩下的球數量是最少的。
Input:
輸入的第一行有一個數字 n ,代表總共有幾顆球。
第二行有長度 n 的字串,依序代表瀚瀚要放入桶中的球。字串由三種字元 'R', 'G', 'B' 組成,R代表紅色球,G代表綠色球,B代表的是藍色球。

限制:

n ≤ 200000
30% 的測試資料滿足: n ≤ 15
Output:
請輸出一行長度為 n 的字串,由字元 'R' 以及字元 'L' 所組成。'R' 代表這一顆球要從右端放入桶裡,'L' 代表這一顆球要從左端放入桶裡。

若存在多種放法能夠使得剩下的球數量最少,請任意輸出一種放法即可。
Sample Input:
9
RGBGGBGBR
Sample Output:
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:
TestTimeMemoryScore
0500ms65536kb
1-1500ms65536kb10
1-2500ms65536kb
1-3500ms65536kb
1-4500ms65536kb
1-5500ms65536kb
2-1500ms65536kb10
2-2500ms65536kb
2-3500ms65536kb
2-4500ms65536kb
2-5500ms65536kb
3-1500ms65536kb10
3-2500ms65536kb
3-3500ms65536kb
3-4500ms65536kb
3-5500ms65536kb
4-1500ms65536kb10
4-2500ms65536kb
4-3500ms65536kb
4-4500ms65536kb
4-5500ms65536kb
5-1500ms65536kb10
5-2500ms65536kb
5-3500ms65536kb
5-4500ms65536kb
5-5500ms65536kb
6-1500ms65536kb10
6-2500ms65536kb
6-3500ms65536kb
6-4500ms65536kb
6-5500ms65536kb
7-1500ms65536kb10
7-2500ms65536kb
7-3500ms65536kb
7-4500ms65536kb
7-5500ms65536kb
8-1500ms65536kb10
8-2500ms65536kb
8-3500ms65536kb
8-4500ms65536kb
8-5500ms65536kb
9-1500ms65536kb10
9-2500ms65536kb
9-3500ms65536kb
9-4500ms65536kb
9-5500ms65536kb
10-1500ms65536kb10
10-2500ms65536kb
10-3500ms65536kb
10-4500ms65536kb
10-5500ms65536kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原