皇家機器人 AI 格鬥大賽即將開打,根據比賽規則,所有參賽者會被隨機排成一列,然後從左右最鄰近的兩個對手開始對戰。若能打敗左(或右)邊的第一個對手,才能繼續跟左(或右)邊的第二個對手對戰。被分配到最左(或右)邊的參賽者運氣不好,他們一開始就只能往右(或左)邊對戰。
瑞奇是格鬥大賽的主播,他很喜歡預測比賽結果。他會搜集參賽者的資料,評估出參賽者的攻擊指數和防禦指數。他認為只要兩個指數有一個高於對手,而且另一個不低於對手(攻擊指數和攻擊指數相比,防禦指數和防禦指數相比),就能贏得該場戰鬥。
以上面的數據為例,有 9 位參賽者。瑞奇預測 5 號參賽者將可贏得三場勝利:戰勝 4號(5 號的兩個指數皆較高)、3(5 號的攻擊指數較高且防禦指數相同)以及 6(5 號的兩個指數皆較高)的對手。5 號無法戰勝 2 號對手,因為 2 號的防禦指數比 5 號的防禦指數高;同理,5 號無法戰勝 7 號的對手,因為 7 號的攻擊指數比 5 號的攻擊指數高。
根據瑞奇的預測方法,請寫一個程式輸出勝場最多的參賽者會贏幾場。以上面的例子來說,他預測的勝場數為:
因此勝場數最多為 8 場。
第一列為一個正整數 N,代表參賽者數。
接下來的 N 列為參賽者資料,第一列為最左邊參賽者的資料,接著依序到最右邊參賽者的資料。每一列有兩個正整數
輸出一正整數,為勝場最多的參賽者會贏幾場。
9 30 30 60 71 60 65 70 44 80 65 25 25 99 44 100 100 18 19
8
3 99 4 100 3 98 5
0
2017北市賽(prob 2)
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~10 | 27 | |
2 | 11~21 | 27 | |
3 | 22~43 | 46 |