大隊接力
問題敘述
成大資訊系在今年春天決定舉辦一場大隊接力競賽，這個大隊接力競賽非常特別，
為了讓大家懷念起國小時曾經玩過的鬼抓人，於是決定在12樓的走廊上舉辦。
走廊的長度總共為n個單位，有m位參賽者，每一位參賽者的位置與速度分別為
pi, si（每一單位時間移動si 單位，移動到走廊第n單位時表示完成比賽），遊戲的規則很
簡單，如果x追到了y（x與y兩人都還沒到達終點前位置相同）那麼y會被淘汰並離
開走廊，而x會繼續參賽並且以每單位時間sy 的速度繼續前進。
注意，有可能會有兩個人一開始就在同樣的位置，那麼視同速度快的人追到了速度
較慢的人，如果兩人的速度相同則編號在前則會以抽籤的方式隨機選出一人淘汰，且如
果兩人同時到達終點則視為兩人都完成比賽。
不過有個附加規則，如果男生追上女生或女生追上男生是不受剛剛的規則限制
的。（也就是說兩人不會有人被淘汰且兩人的速度皆不改變）
Colten 對這場大隊接力非常有興趣，因此事先調查好了所有選手的資料，請你設計
一個程式計算最後總共會有多少人能夠完成比賽。
輸入說明
第一行輸入兩個個正整數n,m。
接下來共輸入m行，每一行依序輸入三個正整數si,pi 與gi，如果gi=0表示該人
為男生，反之如果gi=1則為女生。
測試資料範圍
• 1≤n,si ≤109。
• 1≤m≤2×105。
• 1≤pi ≤n。
• 0≤gi ≤1。
輸出說明
輸出一個整數表示最後總共會有多少人能夠完成比賽。
1
範例測資
範例輸入1
155
631
510
251
330
10151
範例輸出1
3
範例輸入2
103
220
220
220
範例輸出2
1
範例輸入3
52
331
431
範例輸出3
1
2 |
