營火競賽 (APCS 2026-11 中高級)
2.0s 256M營隊要決定隔天由哪一隊負責營地建設，大家決定用一場火把比賽分出結果。
參加的 \(n\) 個人面向中央的營火圍成一圈，依順時針方向給每個人編號 \(1, 2, \ldots, n\)。因為大家都面向營火，每個人左手邊的人就是順時針方向的下一位：第 \(i\) 個人的左手邊是第 \(i+1\) 個人，第 \(n\) 個人的左手邊是第 \(1\) 個人。
隊伍編號是 \(1\)～\(k\)，第 \(i\) 個人是第 \(t_i\) 隊的隊員。比賽開始時，每個人手上的火把都是點燃的，滅火器在第 \(1\) 個人手上。拿著滅火器的人稱為「行動者」，每一回合依照下面的順序進行：
- 行動者由左手邊那一位起，順著順時針一個一個往下看：火把已經熄滅的人跳過，和行動者同一隊的人也跳過。遇到第一位火把點燃、而且和行動者不同隊的人，行動者就把這個人的火把熄滅。火把被熄滅的人之後不會再當行動者。
- 這時如果火把點燃的人全部屬於同一隊，比賽結束，由這一隊負責隔天的營地建設。
- 否則，這一回合的行動者把滅火器往左手邊傳：從行動者的左手邊開始沿順時針方向找，交給第一位火把點燃的人（和行動者同隊也可以），由他當下一回合的行動者。注意找的起點是行動者的左手邊，不是被熄滅的那個人的左手邊。
沿順時針方向找人時，找過第 \(n\) 個人之後接著找第 \(1\) 個人。如果一開始所有人就都是同一隊（\(k = 1\)），比賽不進行任何回合就結束，熄滅的火把數是 \(0\)。
請算出比賽結束時總共有幾支火把被熄滅，還有哪一隊要負責營地建設。
下圖是範例 1 從上往下看的樣子：圓圈裡的數字是編號，圓圈外側小方框裡的數字是這個人的隊伍，每個人都拿著點燃的火把。中間的箭頭是順時針方向，也就是每個人的左手邊。
輸入格式
第一行有兩個整數 \(n\) 與 \(k\)，代表人數與隊伍數。
第二行有 \(n\) 個整數 \(t_1, t_2, \ldots, t_n\)，第 \(i\) 個整數 \(t_i\) 是第 \(i\) 個人所屬的隊伍。
限制
- \(1 \le k \le n \le 2000\)
- \(1 \le t_i \le k\)
- 第 \(1\) 隊到第 \(k\) 隊，每一隊都至少有一個人。
輸出格式
輸出一行，包含兩個整數 \(x\) 與 \(w\)，中間以一個空白隔開：\(x\) 是被熄滅的火把總數，\(w\) 是最後要負責營地建設的那一隊。
評分說明
每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。
| 子題 | 分數 | 額外限制 |
|---|---|---|
| 1 | 40 | \(n < 1000\) |
| 2 | 60 | 無額外限制 |
範例輸入 1
6 3
2 2 1 3 1 2
範例輸出 1
4 2
範例解釋 1
| 回合 | 行動者 | 熄滅誰的火把 |
|---|---|---|
| 1 | 第 1 人（第 2 隊） | 第 3 人（第 1 隊） |
| 2 | 第 2 人（第 2 隊） | 第 4 人（第 3 隊） |
| 3 | 第 5 人（第 1 隊） | 第 6 人（第 2 隊） |
| 4 | 第 1 人（第 2 隊） | 第 5 人（第 1 隊） |
- 第 1 回合：第 1 人左手邊的第 2 人是隊友，跳過；下一位第 3 人是第 1 隊，他的火把被熄滅。接著從第 1 人的左手邊找，第 2 人的火把還點著，滅火器交給第 2 人。
- 第 2 回合：第 2 人往左找，跳過已熄滅的第 3 人，熄滅第 4 人的火把。第 3 隊已經沒有人火把點燃，但還有第 1、2 兩隊，比賽繼續。從第 2 人的左手邊找，第 3、4 人都已熄滅，滅火器交給第 5 人。
- 第 3 回合：第 5 人熄滅左手邊第 6 人的火把。從第 5 人的左手邊找，第 6 人已熄滅，再往下繞回第 1 人，滅火器交給第 1 人。
- 第 4 回合：第 1 人跳過隊友第 2 人、已熄滅的第 3、4 人，熄滅第 5 人的火把。這時火把點燃的只剩第 1、2 人，都是第 2 隊，比賽結束。
一共熄滅 \(4\) 支火把，由第 \(2\) 隊負責營地建設。
範例輸入 2
7 3
1 2 1 3 2 3 2
範例輸出 2
6 2
範例解釋 2
| 回合 | 行動者 | 熄滅誰的火把 |
|---|---|---|
| 1 | 第 1 人（第 1 隊） | 第 2 人（第 2 隊） |
| 2 | 第 3 人（第 1 隊） | 第 4 人（第 3 隊） |
| 3 | 第 5 人（第 2 隊） | 第 6 人（第 3 隊） |
| 4 | 第 7 人（第 2 隊） | 第 1 人（第 1 隊） |
| 5 | 第 3 人（第 1 隊） | 第 5 人（第 2 隊） |
| 6 | 第 7 人（第 2 隊） | 第 3 人（第 1 隊） |
第 4 回合的行動者是最後一位第 7 人，他的左手邊繞回第 1 人；第 1 人和他不同隊，火把被熄滅。第 3 隊在第 3 回合結束時就已經沒有人火把點燃，第 6 回合結束時，火把點燃的只剩第 7 人，比賽結束。一共熄滅 \(6\) 支火把，由第 \(2\) 隊負責營地建設。
題目來源
APCS 2026 年 11 月中高級實作題第 1 題。
官方未公布題本，題敘參考 ecc〈APCS 2026 11月中高級〉 整理，細節可能與正式試題有出入。
