2152 . 拿寶石
TopCoder
Description
好多寶石啊，終於遇到傳說中的隱藏關卡的你，看著面前一堆七彩的寶石，內心無比的興奮。
寶石從上到下總共 $N, (1 \leq N \leq 6666)$ 個排成一堆，其中從上面數來第 $i$ 個的顏色編號為 $A_i, (1 \leq A_i \leq N)$
不同顏色的寶石各自有不同的功能，像是綠色的可以掌握時間，紅色的可以掌握現實。
有個不成文的規則是這樣的，寶石必須從最上面拿，不然它可能會不平衡(假設你旁邊有個能裝無限顆寶石的無限手套，好讓你裝拿下來的寶石)
還有，每次如果要使用一顆寶石，我們必須先將它拿到手上，再用力的彈指頭，之後寶石就會散發出他的魔力（他不會消失，接下來還是可以用），重點在後頭，在寶石散發魔力後，為了保持宇宙的平衡，你必須把你持有的所有寶石一一放回去（從最上面一個一個疊回去），你可以按照任意順序放。
這時牆壁忽然裂了一個大縫，邪惡的復仇者們找上你了，因為你有太多寶石，他們也想要分一些，於是你想要拿寶石對付他們。
$N$ 位復仇者們一一上前攻擊你。要在一個復仇者受傷後，下一個復仇者才會上前。
已知第 $i$ 個前來攻擊你的復仇者害怕顏色編號為 $B_i, (1 \leq B_i \leq N)$ 的寶石所散發出的魔力，所以你決定拿寶石對抗他們。
唯一可惜的是，每當一顆寶石被拿起來一次，就會製造 $1$ 單位的不平衡，脆弱的宇宙最多只能承受 $10^ 5$ 單位的不平衡，所以聰明的你，決定先擬定好拿寶石放寶石的順序，好讓宇宙保持完美平衡
Input Format
第一行一個正整數 $N$ 代表寶石數量
第二行共有 $N$ 個正整數 $A_i$ 之間用一個空白隔開，第 $i$ 個數字代表從上到下第 $i$ 個寶石的顏色
第三行共有 $N$ 個正整數 $B_i$ 之間用一個空白隔開，第 $i$ 個數字代表第 $i$ 位襲擊你的復仇者所害怕的寶石
保證至少存在一種方法 使得你可以打敗所有敵人 又保持宇宙平衡
Output Format
先輸出一個正整數 $K$ 代表你製造了多少不平衡
接下來請按照操作順序輸出 $2K + N$ 行個操作。
如果你拿了寶石堆的一個寶石，請輸出一個字元T
如果你使用了手上的一個寶石，請輸出一個字元U
如果你放回了手上的一個寶石，請輸出一個字元P和一個數字$x$ (中間以一個空白隔開)代表你放回的是顏色編號為 $x$ 的寶石
如果有任何不合理的操作，像是
* 寶石堆空了卻拿寶石
* 手上沒有可以擊退前來的復仇者的寶石時使用寶石
* 放回一個你手上沒有的寶石
* 使用寶石後沒有將寶石歸位
* 等各種不符合題目規範的操作
那你將會拿到一個 WA
Sample Input 1
1 2
2 1
Sample Output 1
T
T
U
P 2
P 1
T
U
P 1
Hints
用完記得放回去喔
關於範測 output
接下來會這樣表示
S : { ... } 代表寶石堆的寶石們
G : { ... } 代表手上的寶石們
F : X 代表目前對手是 X (X == -1 代表對手都輸了)
順序是這樣的:
Round 0--
S : {1, 2}
G : {}
F : 2
Round 1 -- T
S : {2}
G : {1}
F : 2
Round 2 -- T
S : {}
G : {1, 2}
F : 2
Round 3-- U
S : {}
G :{1, 2}
F : 1
Round 4-- P 2 (因為上一輪使用了寶石 所以接下來要先把寶石歸位)
S : {2}
G : {1}
F : 1
Round 5-- P 1
S : {1, 2}
G :{}
F : 1
Round 6-- T (因為上一回合有把寶石全部歸位，所以這回合才能作其他事情
S : {2}
G : {1}
F : 1
Round 7-- U
S : {2}
G : {1}
F : -1
Round 8-- P 1 (這次也是因為上次使用了寶石，所以這回合只能把寶石放回去
S : {1, 2}
G :{}
F : -1
Problem Source
by kevin_zhang
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | $N = 1$ | 1 |
| 2 | 0~10 | $N \leq 100, \forall 1 \leq i < j \leq N, A_i \neq A_j, B_i \neq B_j$ | 9 |
| 3 | 0~20 | $N \leq 1500, \forall 1 \leq i < j \leq N, A_i \neq A_j, B_i \neq B_j$ | 30 |
| 4 | 0~30 | $N \leq 2000$ | 20 |
| 5 | 0~40 | $N \leq 4000$ | 25 |
| 6 | 0~50 | $N \leq 6666$ | 15 |