2262 . 碰撞機器人
TopCoder
Tags
Description
碰撞機器人是一款傳說中比比賽還要累的桌遊，它的規則是這樣的（以下規則與實際規則稍有不同）：
有一個 $16 \times 16$ 的棋盤，四周是圍牆，某些相鄰的格子之間也有牆壁。有四個機器人，分別為藍、綠、紅、黃色，你可以執行最多 $Q$ 個操作，每次操作要選擇一個機器人往上、下、左、右其中一個方向移動，機器人往該方向移動後，就會直線前進直到撞牆或其他機器人為止。
你的目標是通過 $10$ 道關卡，每道關卡的目標皆為讓指定顏色（有些關卡是所有顏色）的機器人移動並停留在指定格子，關卡必須依序完成（完成上一個關卡時，如果下一個關卡的機器人正好停在指定格子上，那視為直接完成下一個關卡，也就是說不一定要做移動到格子的動作，在格子上就好）。所有顏色的機器人都可以經過或暫時停留在指定格子上。在完成一道關卡後，機器人的位置不會回復。
初始盤面與關卡如下：
中間的四個圓形為四種顏色的機器人，而有數字的格子為 $10$ 個關卡中的指定格子，數字顏色為指定顏色，灰色代表所有顏色的機器人到達這個格子皆可通關。
因為怕你的頭破掉，所以出題者很好心的幫你做了一個模擬器。
Input Format
輸入只有一個數字，表示子題編號 $T$，子題的意義請見 Hints。
Output Format
第一行輸出一個整數 $M$，表示你做的操作數量。
接下來輸出 $M$ 行，其中第 $i$ 行為第 $i$ 個操作的資訊，包含兩個由空白隔開的字元 $a_i$ $c_i$，$a_i$ 可以是 BGRY 的其中之一，分別表示藍綠紅黃色的機器人，$c_i$ 可以是 LRUD 的其中之一，分別表示左右上下。
Hints
本題有 $15$ 個子題，差別只有 $Q$ 和需要通過的關卡的不同。
為了獎勵你的努力，對於第 $1$ 到 $5$ 關，你每通過一關就會拿到 $3$ 分；對於第 $6$ 到 $9$ 關，每通過一關會拿到 $4$ 分，如果通過第 $10$ 關會再拿到 $9$ 分。（注意你必須通過前面的關卡，才能通過後面的關卡。）
前十個子題分別對應到十個關卡，也就是說，通過第 $i$ 個關卡就可以拿到子題 $i$ 的分數。這十個子題中 $Q$ 皆為 $10000$。
至於最後五個子題，都必須要完整通過 $10$ 個關卡才能得到分數，每個子題 $12$ 分。令 $S$ 為有做本題並通過所有關卡的隊伍數量，每一隊的最少通關步數由小到大排序為數列 $A$。令數列 $B$ 為：
- $B_{11}=\max(1, \lfloor S/8 \rfloor)$
- $B_{12}=\max(1, \lfloor S/8 \rfloor)$
- $B_{13}=\max(1, \lfloor S/9 \rfloor)$
- $B_{14}=\max(1, \lfloor S/10 \rfloor)$
- $B_{15}=\max(1, \lfloor S/10 \rfloor)$
然後令 $t_i=\sum_{k=i} ^ {15} B_k$，第 $i$（$11 \leq i \leq 15$）個子題的 $Q$ 為 $A_{t_i}$。換句話說，你的最少通關步數必須要是所有隊伍中的前 $t_i$ 名，你才能得到第 $i$ 個子題的分數。
在比賽中，你會於第 $11$ 到 $15$ 個子題獲得 $0$ 分，賽後會 rejudge。
更新：第 $11$ 到 $15$ 個子題的 $Q$ 分別是 $118,113,110,96,90$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | $T=1$ | 3 |
| 2 | 1 | $T=2$ | 3 |
| 3 | 2 | $T=3$ | 3 |
| 4 | 3 | $T=4$ | 3 |
| 5 | 4 | $T=5$ | 3 |
| 6 | 5 | $T=6$ | 4 |
| 7 | 6 | $T=7$ | 4 |
| 8 | 7 | $T=8$ | 4 |
| 9 | 8 | $T=9$ | 4 |
| 10 | 9 | $T=10$ | 9 |
| 11 | 10 | $T=11$ | 12 |
| 12 | 11 | $T=12$ | 12 |
| 13 | 12 | $T=13$ | 12 |
| 14 | 13 | $T=14$ | 12 |
| 15 | 14 | $T=15$ | 12 |