c296. APCS-2016-1029-3定時K彈
Tags : APCS
Accepted rate : 1928人/2901人 ( 66% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-07-22 20:54

Content

「定時 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號是幸運者。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

原題pdf檔(第3頁)

Input

輸入只有一行包含三個正整數,依序為N、M與 K,兩數中間有一個空格分開。其中 1 ≤ K<N。

Output

請輸出幸運者的號碼,結尾有換行符號 。

Sample Input #1
5 2 4
Sample Output #1
3
Sample Input #2
8 3 6
Sample Output #2
4
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :

(範例一說明)

被淘汰的順序是 2、4、1、5,此時5的下一位是3,也是最後剩下的,所以幸運者是3。

(範例二說明)

被淘汰的順序是 3、6、1、5、2、8,此時 8的下一位是 4,所以幸運者是 4。

評分說明

輸入包含若干筆測試資料,每一的執行時間限制 (time limit) 均為 1秒,依正確通過測資筆數給分。其中:

第 1子題組 20分, 1 ≤ N ≤ N 100 ,且 1 ≤ M ≤10 ,K = N-1。

第 2子題組 30 分, 1 ≤ N ≤ 10 ,00 0,且 1 ≤ M ≤1,00 0,000,K = N-1。

第 3子題組 20分, 1 ≤ N ≤ 200 ,000 ,且 1 ≤ M ≤ 1,00 0,00 0,K = N-1。

第 4子題組 30 分, 1 ≤ N ≤ 200 ,000 ,且 1 ≤ M ≤ 1,000 ,00 0,1 ≤ K < N。

應 baluteshih 的提醒,加了1筆 n,m,k接近極限的測資,重評 2019/2/2

Tags:
APCS
出處:
2016年10月APCS [管理者: p3a_owhj (阿普二信) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
37635 edoctopus322 ... (Moon Jam) c296
1127 2023-09-22 20:18
37466 zhoudaniel02 ... (周孝倫) c296
711 2023-09-12 01:18
35648 luray0601@gm ... (QWERTYPIG) c296
C++題解(含想法)
1036 2023-06-10 22:05
31981 seer852741@g ... (St418) c296
1421 2022-09-03 17:02
24714 Hsu0905 (怎麼又是WA) c296
2948 2021-03-17 10:53