現在有 $N$ 個數學家在玩漆彈。身為數學家,他們具有三個特性(純粹為方便題目敘述之用,無意冒犯):
因為他們聽力不怎麼好,所以一聽到「七」彈就想要推廣化,變成了 $M$ 彈;而因為他們不喜歡一直動來動去,他們就將 $M$ 彈改良變成了一個新的遊戲,就叫做「$M$ 彈」。這個 $M$ 彈是遊戲的中心,是一個充滿油漆而上面有寫著數字的一顆球。一旦上面的數字歸零了,$K$ 彈就會噴出在其中的油漆,將拿著 $M$ 彈的人重新上色!與其同名的「$M$ 彈」的遊戲規則如下:
而定義這個遊戲的贏家就是 $M$ 彈爆炸 $K$ 次之後手上拿著 $K$ 彈的那個人。
給定 $N, M, K$,你有辦法知道這個遊戲的贏家是誰嗎?
舉例來說,倘若 $N = 5$,$M = 2$,$K = 4$,則 $[2, 4, 1, 5]$ 將依序出局,最後的勝者為 $3$ 號數學家。
輸入只有一行,包含三個數字,分別是 $N, M, K(1 \leq N \leq 2 \times 10^ 5, 1 \leq M \leq 10^ 6, 1 \leq K < N)$。
此外,這一題有部分給分。
請輸出一個數字,代表最後贏家的編號。
2016 年 10 月 APCS
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 |