TopCoder

Thumb tumblr nlxw0sxc2d1unbsixo1 540
Trash
><

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

13.7% (13/95)

Tags

Description

話說甦蹦構造出他的籬笆設計圖了,但是他很快就發現他並沒有材料。
甦蹦想,既然是傳說的橘子自然要用最好的木頭作籬笆,於是他去請教DBTF。
DBTF表示,世界上最珍貴的木材是位於礦石鎮的黃金木材。
它不會受到風吹雨打而損壞,甚至擁有它會造成全村的嫉妒而好感度下降。

但是甦蹦哪管得了這麼多,他決定去礦石鎮取得一些黃金木材。
走著走著來到了一片森林,這片森林很幽暗,且不時傳出m-m-m-monster kill之類的聲音。
但是在森林深處,甦蹦發現了N棵黃金樹!他決定把每一棵樹都砍倒來取得黃金木材。

可以假設每一棵樹都是完美的圓柱形,並且給了每棵樹底面圓心座標。
甦蹦砍樹的方法只有兩種:H或V。

H表示平行X軸切(橫切),樹會變成兩塊分別往Y正跟Y負方向倒下去。
V表示平行Y軸切(縱切),樹會變成兩塊分別往X正跟X負方向倒下去。

兩種方式倒下去的形狀都會是一個矩形,如上圖所示。

甦蹦想要加快速度,他決定開大決:一次砍下所有的樹,再收集所有的木材回家。

但是他不希望倒下的木材互相壓到或是壓到其他樹的樹根,否則木材會損壞。
(只要有擦到邊或碰到點都算壓到。)

請你提出一種砍樹方案,讓所有樹能成功倒下。若有多組方案,請輸出字典序最小的。

Input Format

第一行有一個正整數N,表示總共有N棵樹。
接下來有N行,第i行會有四個整數Xi, Yi, Ri, Hi。
表示第i棵樹的底面圓心在(Xi, Yi)、半徑Ri、高度Hi。

保證N ≤ 100且所有樹的底面都不會重疊或有交點。
所有數字範圍都是 ≤ 10,000的正整數或0。

Output Format

輸出只有一行包含N個字元。第i個字元Ci表示砍第i棵樹的方式。
無解請輸出一行包含一個字串"so sad"。

Sample Input

3
0 0 4 10
10 10 4 10
10 1006 1 1000

Sample Output

HHV

Hints

對於範例測資,HHV或VVV都是合法的砍樹方案,但是HHV的字典序比較小。

Problem Source

原TIOJ1693 / ABCLS Contest, Problem C

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6