a592. 約瑟夫的遞增輪盤 - 彰化精誠中學

內容

今日，暴君約瑟夫召集了$N$個人圍成一輪盤(圓)，每個人頭上被烙印$1\sim N$的編號，編號相差$1$的人相鄰站。

接下來，約瑟夫要求1號開始報數，報到$k$的那個人就會被處決，之後下一個人再從1開始，一直持續到只剩一個幸運兒為止。

由於玩過很多次這個輪盤遊戲，約瑟夫對於固定的$k$感到無聊，於是改了改規則：$k=1+ai+b$，其中$i$是目前一共有幾個人被處決。

給定$N,a,b$，請求出編號幾的人是幸運兒。

輸入說明

輸入包含一行整數$N,a,b$。

$1\le N\le2\cdot10^5$
$0\le a,b\le2\cdot10^5$

Subtask:

10%: $a=0$
20%: $N\le2000$
70%: 無其他限制。

輸出說明

輸出一個整數$1\le s\le N$，代表遊戲最後活下來的人的編號。

範例輸入 #1

5 0 2

範例輸出 #1

範例輸入 #2

4 2 0

範例輸出 #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 2.0s , <1K
公開測資點#1 (10%): 2.0s , <1K
公開測資點#2 (10%): 2.0s , <1K
公開測資點#3 (10%): 2.0s , <1K
公開測資點#4 (10%): 2.0s , <1K
公開測資點#5 (10%): 2.0s , <1K
公開測資點#6 (10%): 2.0s , <1K
公開測資點#7 (10%): 2.0s , <1K
公開測資點#8 (10%): 2.0s , <1K
公開測資點#9 (10%): 2.0s , <1K

提示：

範例測資1，輪盤遊戲進行如下（畫底線為報1的人）：
$\underset{k=1+0+2}{[\underline1,2,3,4,5]}\to\underset{k=1+0+2}{[1,2,\underline4,5]}\to\underset{k=1+0+2}{[\underline2,4,5]}\to\underset{k=1+0+2}{[\underline2,4]}\to[4]$

範例測資2，輪盤遊戲進行如下：
$\underset{k=1+0+0}{[\underline1,2,3,4]}\to\underset{k=1+2+0}{[\underline2,3,4]}\to\underset{k=1+4+0}{[\underline2,3]}\to[3]$

標籤:

出處:

明達 [管理者：

pusapphire@g... (pusapphire)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」