808 . 到底是幾彈？
TopCoder
Description
現在有 $N$ 個數學家在玩漆彈。身為數學家，他們具有三個特性（純粹為方便題目敘述之用，無意冒犯）：
- 遇到數字就很想要推廣化
- 不喜歡一直動來動去
- 聽力不怎麼好
因為他們聽力不怎麼好，所以一聽到「七」彈就想要推廣化，變成了 $M$ 彈；而因為他們不喜歡一直動來動去，他們就將 $M$ 彈改良變成了一個新的遊戲，就叫做「$M$ 彈」。這個 $M$ 彈是遊戲的中心，是一個充滿油漆而上面有寫著數字的一顆球。一旦上面的數字歸零了，$K$ 彈就會噴出在其中的油漆，將拿著 $M$ 彈的人重新上色！與其同名的「$M$ 彈」的遊戲規則如下：
- 一開始，這 $N$ 個人坐一圈，人們的編號是順時鐘從 $1$ 到 $N$ 依序編號的。
- 一開始，編號 $1$ 的數學家拿著上面的數字寫著 $M$ 的 $M$ 彈，然後他會先將 $M$ 彈的數字減一，再將 $M$ 彈往傳遞給坐在數學家正左邊的人。
- 如果數學家手上的 $M$ 彈上寫的數字剛好歸零，則他會被噴一身的油漆病直接出局，$M$ 彈則給坐在他左手邊的人，遊戲繼續。
- 重複直到 $M$ 彈已經將 $K$ 個人弄出局了。
而定義這個遊戲的贏家就是 $M$ 彈爆炸 $K$ 次之後手上拿著 $K$ 彈的那個人。
給定 $N, M, K$，你有辦法知道這個遊戲的贏家是誰嗎？
舉例來說，倘若 $N = 5$，$M = 2$，$K = 4$，則 $[2, 4, 1, 5]$ 將依序出局，最後的勝者為 $3$ 號數學家。
Input Format
輸入只有一行，包含三個數字，分別是 $N, M, K(1 \leq N \leq 2 \times 10^ 5, 1 \leq M \leq 10^ 6, 1 \leq K < N)$。
此外，這一題有部分給分。
- 對於佔分 $20$ 分的測資，額外保證 $1 \le N \le 100$，且 $1 \le M \le 10$，$K = N - 1$
- 對於佔分 $30$ 分的測資，額外保證 $1 \le N \le 10^ 4$，且 $1 \le M \le 10^ 6$，$K = N - 1$
- 對於佔分 $20$ 分的測資，額外保證 $1 \le N \le 2 \times 10^ 5$，且 $1 \le M \le 10^ 6$，$K = N - 1$
Output Format
請輸出一個數字，代表最後贏家的編號。
Sample Input 1
5 4 3
Sample Output 1
1
Sample Input 2
7 2 4
Sample Output 2
3
Sample Input 3
50 47 2
Sample Output 3
45
Sample Input 4
100 7 99
Sample Output 4
50
Hints
Problem Source
2016 年 10 月 APCS
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~3 | 範例測資 | 0 |
| 2 | 4~8 | $1 \le N \100$，且 $1 \le M \le 10$，$K = N - 1$ | 20 |
| 3 | 4~14 | $1 \le N \10^ 4$，且 $1 \le M \le 10^ 6$，$K = N - 1$ | 30 |
| 4 | 4~19 | $1 \le N \2 \times 10^ 5$，且 $1 \le M \le 10^ 6$，$K = N - 1$ | 20 |
| 5 | 0~28 | 無額外限制 | 30 |