a082. C. 跳躍的波利 - YUTEH ZeroJudge

內容

2015 網際網路程式設計全國大賽國中組初賽

喵喵跟貓貓以前很喜歡玩⼀款線上遊戲。這遊戲裡有很多可愛的怪物，當年很受⼥⽣們的喜愛。例如「波利」就是⾮常受歡迎的可愛怪物之⼀。

最近喵喵和貓貓⼜重新回來懷舊這個童年的回憶，不過他們不是在玩原本的遊戲，⽽是「波利賽跑」這個新的⼩遊戲。

波利是⼀種粉紅⾊的果凍狀⽣物，平常都⽤「跳躍」的⽅式移動，只是⽅向是隨機的很難預測。於是把波利⽤障礙物圍起來之後，像賽⾺⼀樣，來猜看看哪隻波利會最先跳到終點，是個很有趣的⼩遊戲。贏家

會獲得⼀些稀有道具，⽽輸了也不會有什麼損失。所以就算輸了，看著波利跳跳跳也⼗分有趣。

喵喵跟貓貓為了獲得稀有道具，已經盯著波利們跳來跳去好⼀陣⼦了。喵喵跟貓貓都很好奇波利的⾏為是否有可預測的地⽅，畢竟他們最近上的資訊課講到了在電腦上的隨機。⽼師有提到在資訊科學上，要製造真正的隨機是困難的，所以實務上都以偽隨機（pseudo-random）的⽅式來產⽣隨機數。如果產⽣的⽅式太簡單，那麼結果可能會是預測的。於是喵喵跟貓貓開始認真紀錄波利們跳躍的路線，試圖從中去分析並預測波利的動向。

他們對每⼀隻波利會記錄他⼀開始的位置，以及每⼀次跳躍後的位置。⽽在這款遊戲中，座標系是⼆維座標系，所以波利位置可以⽤⼀組座標(x,y)表⽰。

接下來，喵喵跟貓貓想要分析波利的⾏為，可是光⼀隻波利就有很多資料了，他們想要你幫忙寫個程式來處理，你的程式⼀次只會收到⼀隻波利的移動資訊。除此之外，他們也不知道⼀開始要從何下⼿分析，所以打算先從簡單的開始。他們現在想要知道，這隻波利從頭到尾總共改變了幾次⽅向。

他們想請你幫忙寫個程式，給你⼀隻波利的移動記錄，問你這隻波利總共改變⽅向了幾次。

這⼀步改變⽅向的定義是，這⼀步跳躍的⽅向跟上⼀步跳躍的⽅向不同。舉例來說，如果波利依序跳過 (0,0) → (1,1) → (2,2) → (1,2) → (0,2) → (1,1) → (2,0)，可以從下圖發現，波利在第三跟第五步的時候改變了⽅向。

Figure C.1: 第⼀筆範例（邊上的編號表⽰是第幾步）

輸入說明

輸⼊的第⼀⾏有⼀個整數 N，表⽰這隻波利有 N 筆位置紀錄。接下來有 N ⾏，每⼀⾏有兩個整數 x_i,y_i，代表第 i 筆紀錄中波利的位置。

第⼀筆是波利⼀開始的位置，第⼆筆是波利跳第⼀步之後的位置，第三筆是波利跳第⼆步之後的位置，以此類推。

3 ≤ N ≤ 100 • 0 ≤ x,y ≤ 1024
任兩個連續位置紀錄不會相同。也就是說當 1 ≤ i < N 的時候保證 (x_i,y_i) = (̸ x_i₊₁,y_i₊₁)。但要注意兩筆不連續的位置紀錄可能會相同，因為波利可能會過⼀陣⼦跳回同⼀個座標上。

輸出說明

輸出的第⼀⾏須包含⼀個整數 k，表⽰波利總共改變了幾次⽅向。接下來應有 k ⾏，每⾏有⼀個整數 p_i，表⽰第 p_i步的時候改變了⽅向。請由⼩到⼤依序輸出 p_i。

請注意，p_i= 1̸ 。因為根據定義，第⼀步永遠不會是改變⽅向的⼀步。

範例輸入

範例輸出

2
3
5

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (1%): 1.0s , <1K
公開測資點#2 (1%): 1.0s , <1K
公開測資點#3 (1%): 1.0s , <1K
公開測資點#4 (1%): 1.0s , <1K
公開測資點#5 (1%): 1.0s , <1K
公開測資點#6 (1%): 1.0s , <1K
公開測資點#7 (1%): 1.0s , <1K
公開測資點#8 (1%): 1.0s , <1K
公開測資點#9 (1%): 1.0s , <1K
公開測資點#10 (1%): 1.0s , <1K
公開測資點#11 (1%): 1.0s , <1K
公開測資點#12 (1%): 1.0s , <1K
公開測資點#13 (1%): 1.0s , <1K
公開測資點#14 (1%): 1.0s , <1K
公開測資點#15 (1%): 1.0s , <1K
公開測資點#16 (1%): 1.0s , <1K
公開測資點#17 (1%): 1.0s , <1K
公開測資點#18 (1%): 1.0s , <1K
公開測資點#19 (1%): 1.0s , <1K
公開測資點#20 (1%): 1.0s , <1K
公開測資點#21 (1%): 1.0s , <1K
公開測資點#22 (1%): 1.0s , <1K
公開測資點#23 (1%): 1.0s , <1K
公開測資點#24 (1%): 1.0s , <1K
公開測資點#25 (1%): 1.0s , <1K
公開測資點#26 (1%): 1.0s , <1K
公開測資點#27 (1%): 1.0s , <1K
公開測資點#28 (1%): 1.0s , <1K
公開測資點#29 (1%): 1.0s , <1K
公開測資點#30 (1%): 1.0s , <1K
公開測資點#31 (1%): 1.0s , <1K
公開測資點#32 (1%): 1.0s , <1K
公開測資點#33 (1%): 1.0s , <1K
公開測資點#34 (1%): 1.0s , <1K
公開測資點#35 (1%): 1.0s , <1K
公開測資點#36 (1%): 1.0s , <1K
公開測資點#37 (1%): 1.0s , <1K
公開測資點#38 (1%): 1.0s , <1K
公開測資點#39 (1%): 1.0s , <1K
公開測資點#40 (1%): 1.0s , <1K
公開測資點#41 (1%): 1.0s , <1K
公開測資點#42 (1%): 1.0s , <1K
公開測資點#43 (1%): 1.0s , <1K
公開測資點#44 (1%): 1.0s , <1K
公開測資點#45 (1%): 1.0s , <1K
公開測資點#46 (1%): 1.0s , <1K
公開測資點#47 (1%): 1.0s , <1K
公開測資點#48 (1%): 1.0s , <1K
公開測資點#49 (1%): 1.0s , <1K
公開測資點#50 (1%): 1.0s , <1K
公開測資點#51 (1%): 1.0s , <1K
公開測資點#52 (1%): 1.0s , <1K
公開測資點#53 (1%): 1.0s , <1K
公開測資點#54 (1%): 1.0s , <1K
公開測資點#55 (1%): 1.0s , <1K
公開測資點#56 (1%): 1.0s , <1K
公開測資點#57 (1%): 1.0s , <1K
公開測資點#58 (1%): 1.0s , <1K
公開測資點#59 (1%): 1.0s , <1K
公開測資點#60 (1%): 1.0s , <1K
公開測資點#61 (1%): 1.0s , <1K
公開測資點#62 (1%): 1.0s , <1K
公開測資點#63 (1%): 1.0s , <1K
公開測資點#64 (1%): 1.0s , <1K
公開測資點#65 (1%): 1.0s , <1K
公開測資點#66 (1%): 1.0s , <1K
公開測資點#67 (1%): 1.0s , <1K
公開測資點#68 (1%): 1.0s , <1K
公開測資點#69 (1%): 1.0s , <1K
公開測資點#70 (1%): 1.0s , <1K
公開測資點#71 (1%): 1.0s , <1K
公開測資點#72 (1%): 1.0s , <1K
公開測資點#73 (1%): 1.0s , <1K
公開測資點#74 (1%): 1.0s , <1K
公開測資點#75 (1%): 1.0s , <1K
公開測資點#76 (1%): 1.0s , <1K
公開測資點#77 (1%): 1.0s , <1K
公開測資點#78 (1%): 1.0s , <1K
公開測資點#79 (1%): 1.0s , <1K
公開測資點#80 (2%): 1.0s , <1K
公開測資點#81 (2%): 1.0s , <1K
公開測資點#82 (2%): 1.0s , <1K
公開測資點#83 (2%): 1.0s , <1K
公開測資點#84 (2%): 1.0s , <1K
公開測資點#85 (2%): 1.0s , <1K
公開測資點#86 (2%): 1.0s , <1K
公開測資點#87 (2%): 1.0s , <1K
公開測資點#88 (2%): 1.0s , <1K
公開測資點#89 (2%): 1.0s , <1K

提示：

標籤:

2015國中組初賽

出處:

NPSC [管理者：

zero (管理員)

]

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