TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

25.0% (1/4)

Tags

Description

現在有 $N$ 個數學家在玩漆彈。身為數學家,他們具有三個特性(純粹為方便題目敘述之用,無意冒犯):

  1. 遇到數字就很想要推廣化
  2. 不喜歡一直動來動去
  3. 聽力不怎麼好

因為他們聽力不怎麼好,所以一聽到「七」彈就想要推廣化,變成了 $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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 5
1 1000 262144 65536 1 5
2 1000 262144 65536 1 5
3 1000 262144 65536 1 5
4 1000 262144 65536 2 3 4 5
5 1000 262144 65536 2 3 4 5
6 1000 262144 65536 2 3 4 5
7 1000 262144 65536 2 3 4 5
8 1000 262144 65536 2 3 4 5
9 1000 262144 65536 3 4 5
10 1000 262144 65536 3 4 5
11 1000 262144 65536 3 4 5
12 1000 262144 65536 3 4 5
13 1000 262144 65536 3 4 5
14 1000 262144 65536 3 4 5
15 1000 262144 65536 4 5
16 1000 262144 65536 4 5
17 1000 262144 65536 4 5
18 1000 262144 65536 4 5
19 1000 262144 65536 4 5
20 1000 262144 65536 5
21 1000 262144 65536 5
22 1000 262144 65536 5
23 1000 262144 65536 5
24 1000 262144 65536 5
25 1000 262144 65536 5
26 1000 262144 65536 5
27 1000 262144 65536 5
28 1000 262144 65536 5