TopCoder

Caido
Waimai

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

50.0% (2/4)

Tags

Description

碰撞機器人是一款傳說中比比賽還要累的桌遊,它的規則是這樣的(以下規則與實際規則稍有不同):

有一個 16×16 的棋盤,四周是圍牆,某些相鄰的格子之間也有牆壁。有四個機器人,分別為藍、綠、紅、黃色,你可以執行最多 Q 個操作,每次操作要選擇一個機器人往上、下、左、右其中一個方向移動,機器人往該方向移動後,就會直線前進直到撞牆或其他機器人為止。

你的目標是通過 10 道關卡,每道關卡的目標皆為讓指定顏色(有些關卡是所有顏色)的機器人移動並停留在指定格子,關卡必須依序完成(完成上一個關卡時,如果下一個關卡的機器人正好停在指定格子上,那視為直接完成下一個關卡,也就是說不一定要做移動到格子的動作,在格子上就好)。所有顏色的機器人都可以經過或暫時停留在指定格子上。在完成一道關卡後,機器人的位置不會回復

初始盤面與關卡如下:

中間的四個圓形為四種顏色的機器人,而有數字的格子為 10 個關卡中的指定格子,數字顏色為指定顏色,灰色代表所有顏色的機器人到達這個格子皆可通關。

因為怕你的頭破掉,所以出題者很好心的幫你做了一個模擬器

Input Format

輸入只有一個數字,表示子題編號 T,子題的意義請見 Hints。

Output Format

第一行輸出一個整數 M,表示你做的操作數量。

接下來輸出 M 行,其中第 i 行為第 i 個操作的資訊,包含兩個由空白隔開的字元 ai ciai 可以是 BGRY 的其中之一,分別表示藍綠紅黃色的機器人,ci 可以是 LRUD 的其中之一,分別表示左右上下。

Hints

本題有 15 個子題,差別只有 Q 和需要通過的關卡的不同。

為了獎勵你的努力,對於第 15 關,你每通過一關就會拿到 3 分;對於第 69 關,每通過一關會拿到 4 分,如果通過第 10 關會再拿到 9 分。(注意你必須通過前面的關卡,才能通過後面的關卡。)

前十個子題分別對應到十個關卡,也就是說,通過第 i 個關卡就可以拿到子題 i 的分數。這十個子題中 Q 皆為 10000

至於最後五個子題,都必須要完整通過 10 個關卡才能得到分數,每個子題 12 分。令 S 為有做本題並通過所有關卡的隊伍數量,每一隊的最少通關步數由小到大排序為數列 A。令數列 B 為:

  • B11=max(1,S/8)
  • B12=max(1,S/8)
  • B13=max(1,S/9)
  • B14=max(1,S/10)
  • B15=max(1,S/10)

然後令 ti=k=i15Bk,第 i11i15)個子題的 QAti。換句話說,你的最少通關步數必須要是所有隊伍中的前 ti 名,你才能得到第 i 個子題的分數。

在比賽中,你會於第 1115 個子題獲得 0 分,賽後會 rejudge。

更新:第 1115 個子題的 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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 3
3 1000 65536 65536 4
4 1000 65536 65536 5
5 1000 65536 65536 6
6 1000 65536 65536 7
7 1000 65536 65536 8
8 1000 65536 65536 9
9 1000 65536 65536 10
10 1000 65536 65536 11
11 1000 65536 65536 12
12 1000 65536 65536 13
13 1000 65536 65536 14
14 1000 65536 65536 15