APCS 2016.10.29 第 3 題 定時 K 彈

APCS 2016.10.29
第 3 題 定時 K 彈
問題描述
「定時 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，請寫程式計算出誰是幸運者。

輸入格式
輸入只有一行包含三個正整數，依序為 N、M 與 K，兩數中間有一個空格分開。其中
1 ≤ K<N。
輸出格式
請輸出幸運者的號碼，結尾有換行符號。
範例一：輸入
5 2 4
範例一：正確輸出
3
（說明）
被淘汰的順序是 2、4、1、5，此時 5 的
下一位是 3，也是最後剩下的，所以幸運
者是 3。
範例二：輸入
8 3 6
範例二：正確輸出
4
（說明）
被淘汰的順序是 3、6、1、5、2、8，此
時 8 的下一位是 4，所以幸運者是 4。
評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依
正確通過測資筆數給分。其中：
第 1 子題組 20 分，1 ≤ N ≤ 100，且 1 ≤ M ≤ 10，K = N-1。
第 2 子題組 30 分，1 ≤ N ≤ 10,000，且 1 ≤ M ≤ 1,000,000，K = N-1。
第 3 子題組 20 分，1 ≤ N ≤ 200,000，且 1 ≤ M ≤ 1,000,000，K = N-1。
第 4 子題組 30 分，1 ≤ N ≤ 200,000，且 1 ≤ M ≤ 1,000,000，1 ≤ K < N。

//-------------------------------(⇊⇊code⇊⇊)-------------------------------------

#include<stdio.h>

int main() {
int m=0,k=0,n=0;
scanf("%d %d %d",&n,&m,&k);

{
int a[n+1]= {} ;
int j=0,c=0;
while(j<k) {
int l=0;
while(l<m) {
c++;
if(a[c%n?c%n:n]==0)
l++;
}
a[c%n?c%n:n]++;
j++;
}
int b=0;

for(int i=c%n?c%n:n; i<=n; i++) {
if(a==0) {

b=i;
break;
}
}

if(b==0)
for(int i=1; i<c%n?c%n:n; i++) {

if(a==0) {

b=i;
break;
}
}
printf("%d",b);
}

}