話說甦蹦構造出他的籬笆設計圖了,但是他很快就發現他並沒有材料。
甦蹦想,既然是傳說的橘子自然要用最好的木頭作籬笆,於是他去請教DBTF。
DBTF表示,世界上最珍貴的木材是位於礦石鎮的黃金木材。
它不會受到風吹雨打而損壞,甚至擁有它會造成全村的嫉妒而好感度下降。
但是甦蹦哪管得了這麼多,他決定去礦石鎮取得一些黃金木材。
走著走著來到了一片森林,這片森林很幽暗,且不時傳出m-m-m-monster kill之類的聲音。
但是在森林深處,甦蹦發現了N棵黃金樹!他決定把每一棵樹都砍倒來取得黃金木材。
可以假設每一棵樹都是完美的圓柱形,並且給了每棵樹底面圓心座標。
甦蹦砍樹的方法只有兩種:H或V。
H表示平行X軸切(橫切),樹會變成兩塊分別往Y正跟Y負方向倒下去。
V表示平行Y軸切(縱切),樹會變成兩塊分別往X正跟X負方向倒下去。
兩種方式倒下去的形狀都會是一個矩形,如上圖所示。
甦蹦想要加快速度,他決定開大決:一次砍下所有的樹,再收集所有的木材回家。
但是他不希望倒下的木材互相壓到或是壓到其他樹的樹根,否則木材會損壞。
(只要有擦到邊或碰到點都算壓到。)
請你提出一種砍樹方案,讓所有樹能成功倒下。若有多組方案,請輸出字典序最小的。
第一行有一個正整數N,表示總共有N棵樹。
接下來有N行,第i行會有四個整數Xi, Yi, Ri, Hi。
表示第i棵樹的底面圓心在(Xi, Yi)、半徑Ri、高度Hi。
保證N ≤ 100且所有樹的底面都不會重疊或有交點。
所有數字範圍都是 ≤ 10,000的正整數或0。
輸出只有一行包含N個字元。第i個字元Ci表示砍第i棵樹的方式。
無解請輸出一行包含一個字串"so sad"。
對於範例測資,HHV或VVV都是合法的砍樹方案,但是HHV的字典序比較小。
原TIOJ1693 / ABCLS Contest, Problem C
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 16 |
2 | 1 | 16 |
3 | 2 | 16 |
4 | 3 | 16 |
5 | 4 | 16 |
6 | 5 | 20 |