TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

62.5% (5/8)

Tags

Description

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

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

因為他們聽力不怎麼好,所以一聽到「七」彈就想要推廣化,變成了 M 彈;而因為他們不喜歡一直動來動去,他們就將 M 彈改良變成了一個新的遊戲,就叫做「M 彈」。這個 M 彈是遊戲的中心,是一個充滿油漆而上面有寫著數字的一顆球。一旦上面的數字歸零了,K 彈就會噴出在其中的油漆,將拿著 M 彈的人重新上色!與其同名的「M 彈」的遊戲規則如下:

  • 一開始,這 N 個人坐一圈,人們的編號是順時鐘從 1N 依序編號的。
  • 一開始,編號 1 的數學家拿著上面的數字寫著 MM 彈,然後他會先將 M 彈的數字減一,再將 M 彈往傳遞給坐在數學家正左邊的人
  • 如果數學家手上的 M 彈上寫的數字剛好歸零,則他會被噴一身的油漆病直接出局,M 彈則給坐在他左手邊的人,遊戲繼續。
  • 重複直到 M 彈已經將 K 個人弄出局了。

而定義這個遊戲的贏家就是 M 彈爆炸 K 次之後手上拿著 K 彈的那個人。

給定 N,M,K,你有辦法知道這個遊戲的贏家是誰嗎?

舉例來說,倘若 N=5M=2K=4,則 [2,4,1,5] 將依序出局,最後的勝者為 3 號數學家。

Input Format

輸入只有一行,包含三個數字,分別是 N,M,K(1N2×105,1M106,1K<N)

此外,這一題有部分給分。

  • 對於佔分 20 分的測資,額外保證 1N100,且 1M10K=N1
  • 對於佔分 30 分的測資,額外保證 1N104,且 1M106K=N1
  • 對於佔分 20 分的測資,額外保證 1N2×105,且 1M106K=N1

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 1N\100,且 1M10K=N1 20
3 4~14 1N\104,且 1M106K=N1 30
4 4~19 1N\2×105,且 1M106K=N1 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