TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

42.9% (3/7)

Submission's AC Ratio

17.3% (9/52)

Tags

Description

楓之谷是個平面捲動的線上遊戲,在這遊戲裡面,除了讓玩家不停地打怪物賺經驗值升級以外,還安排了一些「任務」給玩家解,只要完成了,就會有特別的獎勵。有的任務是收集一定數量的特定物品,而有的任務叫作「忍耐任務」。

顧名思義,忍耐任務就是在考驗玩家的耐性。在忍耐任務裡面,玩家會被差派到特別的地圖去,在這種地圖裡面,也許還是會有怪物,並且會有一些飛來飛去的飛行物,像是飛鏢一類的,然而當它們撞到玩家的時候,玩家幾乎不會損血,因為它們存在的意義並不是要將玩家擊斃,而只是要阻礙玩家前進。在這樣的地圖裡,通常會安排十分難走的路,例如說有非常小的平台來讓玩家跳躍,或是不時會有長矛刺到的繩梯,而且在路途上還安排了會阻礙玩家的飛行物和怪物,玩家只要一個不小心,就會掉下來。這路途常安排得十分漫長,而且一掉下來,就要重頭來過。而玩家的最終目標,就是要走完全程,拿到指定的物品,或是和指定的人物說話。

很難想像什麼人會喜歡解這種任務,可是真的有人熱中於此,甚至成為此間箇中高中。暱稱是阿特珞的這位玩家,就是這樣的一個奇人,她不但解自己接的忍耐任務,還幫忙別人解,甚至挑戰十五分鐘內解三個,熟練的程度甚至在遊戲中曾讓別人懷疑她是否使用外掛輔助程式。

成功的行動寓於周詳的計畫,在解一個任務之前,她已將這個地圖的底細調查清楚了。知道哪些地方有平台可以站立,也知道所有的飛行物體的軌跡和週期。然後她擬定了一連串的移動計畫,也就是在什麼時候要做什麼動作,像是蹲下,移動,或是跳躍。提供了周詳的地圖與計劃內容後,她想請你們寫一個程式,判斷她所擬定的計劃是否能成功執行。

Input Format

在這輸入的資料裡,總共包含一個場景,還有若干個移動計畫。我們假設這個場景是放在一個無窮大的二維的 $\text{X-Y}$ 坐標系上。輸入的第一行將有一個整數 $L (1 ≤ L ≤ 20)$,代表之後將會輸入 $L$ 個水平線段,它們彼此不會相交或接觸。這些線段就是在地圖中可以站立的地方,(另外在跳躍的時候並不會因為頂到線段而掉下來。甚至當你正在往上「飛」的時候,你可以穿越上方的線段,直到下落的時候,才會停在線段上。) 每一行會包含一條線段的輸入資料,共有三個數 (可能有小數點),第一個數是這個線段的 $\text{Y}$ 坐標,第二個數是左側 (較小) 端點的 $\text{X}$ 坐標,第三個數是右側端點的 $\text{X}$ 坐標。

接著這些線段的輸入資料之後,會輸入一行剛好有一個整數 $N (0 ≤ N ≤ 20)$,表示接下來共有 $N$ 行輸入資料分別表示這 $N$ 個怪物或是飛行物體的資料。在我們測試的資料裡,只考慮兩種軌跡:第一種是在線段上作簡諧運動(小心是簡諧運動而不是等速往返的運動),第二種是在圓上作等速率圓周運動。當一列以 $1$ 個字元 h 起始時,表示其是個在線段上作簡諧運動的怪物。接下來分別是起點和另一端點的 $\text{X}$ 和 $\text{Y}$座標,然後是週期,表示來回一次的秒數。當一列以 $1$ 個字元 c 起始時,表示其是個進行圓周運動的飛行物。接下來是圓心的 $\text{X}$ 和 $\text{Y}$ 坐標,再來是半徑,以及週期的秒數 (假設起點都是圓上最右邊那一個點,依逆時針方向運動)。

最後會輸入兩個數,代表一開始的時候玩家所在位置的 $\text{X}$ 和 $\text{Y}$。注意,$\text{X}$ 是往右增加,而 $\text{Y}$ 是往上增加的。

待這些場景資料都描述完了,接下來又會輸入一列整數,表示有幾個計畫。每一個計畫會佔一列,是一連串的動作描述。每一個動作都是一個動作種類,然後是持續時間。動作分為下列數種: 沒動作 (none),往右走 (rwalk),往左走 (lwalk),往上跳 (ujump),往右跳 (rjump),往左跳 (ljump)。

現在要說我們打算用來模擬的方法。首先要注意的是,當玩家身在空中的時候,所有的動作都是沒有效果的,就好比玩家正在往下掉的時候,即使方向鍵一直壓著,也不會有作用。當玩家站在地上的時候,往左往右走的命令會使他以秒速一單位長的方式行走,往左往右跳的命令會使他以 $45°$ 仰角,初速秒速二單位長的方式跳,往上跳的命令是初速秒速二單位長垂直往上。假設在這個遊戲裡頭重力加速度是二單位長每秒平方,當玩家走到平台的邊緣,或是開始跳躍以後,就會以這樣的重力加速度往下掉,而水平方向的速度是以他離地,或是起跳的那一刻來算。

至於和飛行物體碰撞的檢查,理論上是任何時候都要檢查,但是這太花時間了,所以我們自己設定是每 $0.1$ 秒檢查一次,如果玩家的位置和某個飛行物體的距離少於 $0.5$ 單位的話,就算是有碰撞。(如果你執意要檢查所有的時間點,仍然可以通過測試,題目只是保證對於輸入的資料,只要每 $0.1$ 秒檢查一次,就可以得到正確的結果)

Output Format

如果玩家能夠成功而順暢地執行完所有的命令,最後停下來以後可以靜止地站立一秒鐘,就算是成功,此時請輸出一列 Y,否則請輸出一列 N。不用考慮玩家恰好站立在平台的邊緣,或是落下來的時候恰好落在邊緣,也不用考慮一直下掉,卻踩不到平台的問題,輸入資料不會有這種情形。

Sample Input 1

2
0 0 4
0 5 8
2
h 100 100 200 200 1
h 1.5 -1 1.5 1 4
0.5 0.0001
2
rwalk 3 rjump 0.1 rwalk 1
none 1 rwalk 3 rjump 0.1 rwalk 1

Sample Output 1

N
Y

Hints

註:這一年的 NPSC 非常困難。只要正確兩題就可以進入決賽,決賽的第一名只寫出了三題…當然初賽時南部的學術網路掛掉也是記分板顏色單調的主因之一。

※2008/01/22 範例輸入修正:感謝 hallogameboy。

Problem Source

原 TIOJ1065 / NPSC2005 初賽 (prob A)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1