r990. PH. ENDOR - 高中生程式解題系統

內容

在森林密布的衛星恩多上，根據吉尼斯世界紀錄記載，有一根銀河系最長的木棍。這根長 L 米的木棍上，有 N 隻活潑可愛的變色龍。每隻變色龍都以 1 米/秒的恆定速度沿著木棍向左或向右移動，並且被塗成了 K 種顏色中的一種。

已知恩多星的變色龍信奉古老的螞蟻法則，該法則規定，沿著棍子行走必須一直走到棍子的盡頭（即離開棍子），並且當與其他變色龍發生碰撞時，必須轉身 180 度，然後朝相反的方向繼續行走。此外，當一隻向左移動的 a 色變色龍與一隻向右移動的 b 色變色龍發生碰撞後，碰撞前向左移動的變色龍會變成碰撞前向右移動的變色龍的顏色（即 b 色），而碰撞前向右移動的變色龍則會變成新的顏色（a + b mod K）。

如果已知所有變色龍的初始位置、顏色和移動方向，請確定每種顏色的變色龍在離開木棍之前所走的總行程。

輸入說明

輸入的第一行包含來自任務的整數 N、K 和 L (1 ≤ N ≤ 100 000, 1 ≤ K ≤ 40, 1 ≤ L ≤ 1 000 000)。接下來的 N 行中，第 i 行包含整數 di (0 ≤ di ≤ L)，表示第 i 隻變色龍與木棍左端的距離，接著是整數 bi (0 ≤ bi ≤ K − 1)，表示第 i 隻變色龍的顏色，以及字符「L」（左）或「D」（右），表示第 i 隻變色龍的移動方向。所有整數 di 都是唯一的，並且嚴格按升序排列。

輸出說明

輸出必須包含 K 行，第 i 行包含顏色為 i 的變色龍的總行程。

範例輸入 #1

2 3 10
0 0 D
10 1 L

範例輸出 #1

10.0
10.0
0.0

範例輸入 #2

範例輸出 #2

10.0
4.0
1.0

範例輸入 #3

範例輸出 #3

2.5
4.0
2.5
4.0

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 0.1s , <1M
不公開測資點#1 (5%): 0.1s , <1M
不公開測資點#2 (5%): 0.1s , <1M
不公開測資點#3 (5%): 0.1s , <1M
不公開測資點#4 (5%): 0.1s , <1M
不公開測資點#5 (5%): 0.1s , <1M
不公開測資點#6 (5%): 0.1s , <1M
不公開測資點#7 (5%): 0.1s , <1M
不公開測資點#8 (5%): 0.1s , <1M
不公開測資點#9 (5%): 0.1s , <1M
不公開測資點#10 (5%): 0.1s , <1M
不公開測資點#11 (5%): 0.1s , <1M
不公開測資點#12 (5%): 0.1s , <1M
不公開測資點#13 (5%): 0.1s , <1M
不公開測資點#14 (5%): 0.1s , <1M
不公開測資點#15 (5%): 0.1s , <1M
不公開測資點#16 (5%): 0.1s , <1M
不公開測資點#17 (5%): 0.1s , <1M
不公開測資點#18 (5%): 0.1s , <1M
不公開測資點#19 (5%): 0.1s , <1M

提示：

對第一個例子的解釋：兩隻變色龍在棍子中間行進5公尺後發生碰撞。碰撞後，兩隻變色龍都改變了運動方向。碰撞後向右移動的變色龍標示為0，而碰撞後向左移動的變色龍則標示為1。

標籤:

DP contest Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」