回分類題庫
z043: C. 跳躍的波利
關鍵字: 2015 NPSC 國中組初試

測資點 : 10 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 10 Times / 10 Users | Submit : 54 Times / 18 Users | Accepted rate : 56%
題目加入時間 : 2018-11-08 17:15

Content: 简体中文

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

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

波利是種粉紅的果凍狀物,平常都「跳躍」的式移動, 只是向是隨機的很難預測。於是把波利障礙物圍起來之後,像賽 樣,來猜看看哪隻波利會最先跳到終點,是個很有趣的遊戲。贏家 會獲得些稀有道具,輸了也不會有什麼損失。所以就算輸了,看著波利跳跳跳也分有趣。

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

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

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

他們想請你幫忙寫個程式,給你隻波利的移動記錄,問你這隻波利總共改變向了幾次。步改變向的定義是,這步跳躍的向跟上步跳躍向不同。

舉例來說,如果波利依序跳過(0,0) (1,1) (2,2) (1,2) (0,2) (1,1) (2,0),可以從下圖發現,波利在第三跟第五步的時候改變了向。

 圖x

Input:

的第⼀⾏個整數N,表這隻波利有N 筆位置紀錄。接下來有N ,每⼀⾏有兩個整數 xi,yi,代表第i筆紀錄中波利的位置。

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

• 3 N 100

0 x,y 1024

任兩個連續位置紀錄不會相同。也就是說當1 i < N的時候保證(xi,yi) ≠ (xi+1,yi+1)。但要注意兩筆不連續的位置紀錄可能會相同,因為波利可能會過跳回同個座標上。

Output:

輸出的第⼀⾏須包含個整數k,表波利總共改變了幾次向。接下來應有k,每個整數 pi,表pi步的時候改變了向。請由依序輸出pi。 請注意,pi 1。因為根據定義,第步永遠不會是改變向的步。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
例1:
7
0 0
1 1
2 2
1 2
0 2
1 1
2 0

例2:
5
0 0
0 1
1 1
1 0
0 0

Sample Output :

例1:
2
3
5

例2:
3
2
3
4

Hint :

Author :

2015 NPSC 國中組初試 (管理員:Chang)

  Solve it!   Status Forum