定時 K 彈 (APCS 2016-10 中高級)

「定時 \(K\) 彈」是一個團康遊戲，\(N\) 個人圍成一圈，由 1 號依序到 \(N\) 號，從 1 號開始依序傳遞一枚玩具炸彈，每次到第 \(M\) 個人就會爆炸，此人即淘汰，被淘汰的人要離開圓圈，然後炸彈再從該淘汰者的下一個開始傳遞。遊戲之所以稱 \(K\) 彈是因為這枚炸彈只會爆 \(K\) 次，在第 \(K\) 次爆炸後，遊戲即停止，而此時在第 \(K\) 個淘汰者的下一位遊戲者被稱為幸運者，通常就會要求表演節目。例如 \(N=5\)，\(M=2\)，如果 \(K=2\)，炸彈會爆兩次，被爆炸淘汰的順序依是 2 與 4（參見下圖），這時 5 號就是幸運者。如果 \(K=3\)，剛才的遊戲會繼續，第三個淘汰是 1 號，所以幸運者是 3 號。如果 \(K=4\)，下一輪淘汰 5 號，所以 3 號是幸運者。

輸入格式

輸入只有一行包含三個正整數，依序為 \(N\)、\(M\) 與 \(K\)，兩數中間有一個空格分開。其中 \(1 \le K<N\)。

輸出格式

請輸出幸運者的號碼，結尾有換行符號。

範例輸入 1

5 2 4

範例輸出 1

3

範例輸入 2

8 3 6

範例輸出 2

4

範例解釋 1

被淘汰的順序是 2、4、1、5，此時 5 的下一位是 3，也是最後剩下的，所以幸運者是 3。

範例解釋 2

被淘汰的順序是 3、6、1、5、2、8，此時 8 的下一位是 4，所以幸運者是 4。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制 (time limit) 均為 1 秒，依正確通過測資筆數給分。其中：

第 1 子題組 20 分， \(1 \le N \le 100\)，且 \(1 \le M \le 10\)，\(K = N-1\)。

第 2 子題組 30 分， \(1 \le N \le 10,000\)，且 \(1 \le M \le 1,000,000\)，\(K = N-1\)。

第 3 子題組 20 分， \(1 \le N \le 200,000\)，且 \(1 \le M \le 1,000,000\)，\(K = N-1\)。

第 4 子題組 30 分， \(1 \le N \le 200,000\)，且 \(1 \le M \le 1,000,000\)，\(1 \le K < N\)。

題目來源

APCS 2016 年 10 月 29 日程式實作題第 3 題「定時 K 彈」，亦收錄於 ZeroJudge c296。

• APCS 官方歷屆試題（2016/10/29 實作題 PDF）