# APCS實作題2016年10月第3題：定時K彈
> 第1版：2023年2月10日
> 第2版：2023年6月12日，加上 C++ 程式碼
> 作者：王一哲
> 題目來源：[105年10月29日實作題第3題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/11/1051029APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c296)
<br />
## 題目
### 問題描述
「定時 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，請你計算出誰是幸運者。
<br />
<img height="80%" width="80%" src="https://i.imgur.com/Xp5Xk4q.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />
### 輸入格式
輸入只有一行包含三個正整數，依序為 N、M 與 K，兩數中間有一個空格分開。其中 $1 \leq K < N$。
<br />
### 輸出格式
請輸出幸運者的號碼，結尾有換行符號。
<br />
### 範例一：輸入
```
5 2 4
```
### 範例一：正確輸出
```
3
```
（說明）被淘汰的順序是 2、4、1、5，此時 5 的下一位是 3，也是最後剩下的，所以幸運者是 3。
<br />
### 範例二：輸入
```
8 3 6
```
### 範例二：正確輸出
```
4
```
（說明）被淘汰的順序是 3、6、1、5、2、8，此時 8 的下一位是 4，所以幸運者是 4。
<br />
### 評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依
正確通過測資筆數給分。其中：
- 第 1 子題組 20 分，$1 \leq N \leq 100$，且 $1 \leq M \leq 10$，$K = N-1$。
- 第 2 子題組 30 分，$1 \leq N \leq 10,000$，且 $1 \leq M \leq 1,000,000$，$K = N-1$。
- 第 3 子題組 20 分，$1 \leq N \leq 200,000$，且 $1 \leq M \leq 1,000,000$，$K = N-1$。
- 第 4 子題組 30 分，$1 \leq N \leq 200,000$，且 $1 \leq M \leq 1,000,000$，$1 \leq K < N$。
<br />
## 參考答案
### 方法1
比較直接的作法，用串列 (list) 儲存資料，於迴圈中模擬整個運作過程，但是在 ZeroJudge #4 測資會超時。
```python=
N, M, K = map(int, input().split())
num = N
count = 0
idx = 0
data = [i for i in range(N)]
while num > N - K:
count += 1
idx += 1
if idx >= num: idx -= num
if count % M == 0:
del(data[idx])
idx -= 1
num -= 1
count = 0
idx += 1
if idx >= num: idx -= num
print(data[idx])
```
<br />
1. 第5行：産生長度為N的一維串列，元素為 0、1、2、…、N-1。
2. 第7 ~ 15行：while 迴圈
1. 在串列長度（人數） num > N - K 時繼續執行 while 迴圈
2. 迴圈中先將次數 count 加1、索引值 idx 加1
3. 如果 idx >= num，則 idx 要回到串列最前方，將 idx 值減去 num。
4. 如果 count % M == 0，炸彈爆炸，此人出局，del(data[idx])。下次執行 while 迴圈時，炸彈傳到下一個人手上，次數為1，所以先將 idx 減1，退回上一個人。人數 num 減1。次數 count 歸0。
3. 第17 ~ 19行：先將 idx 加1，再檢查 idx 是否要回到串列最前方，最後印出幸運者的編號。
<br /><br />
### 方法2
比較直接的作法，用串列 (list) 儲存資料，用佇列的概念運作，於迴圈中模擬整個運作過程，但是在 ZeroJudge #4 測資會超時。
```python=
N, M, K = map(int, input().split())
men = [i+1 for i in range(N)]
count = 0
#man = men.pop(0)
#men.append(man)
while count < K:
for i in range(M):
man = men.pop(0)
if i == M-1: count += 1
else: men.append(man)
#print(men)
print(men[0])
```
<br /><br />
即使改用 C++ 及佇列 (queue)，仍然在 ZeroJudge #4 測資會超時。
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main() {
int N, M, K; cin >> N >> M >> K;
queue<int> men;
for(int i=1; i<=N; i++) men.push(i);
int count = 0;
while(count < K) {
for(int i=0; i<M; i++) {
int man = men.front(); men.pop();
if (i == M-1) count++;
else men.push(man);
}
}
cout << men.front() << endl;
return 0;
}
```
<br /><br />
### 方法3
自訂類別 Noed，再用 Noed 産生環狀串列 (linked list) 儲存資料，於迴圈中模擬整個運作過程，但是在 ZeroJudge #4 測資會超時。
```python=
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
def creatLinkedList(n):
head = Node(1)
pre = head
for i in range(2, n+1):
newNode = Node(i)
pre.next = newNode
pre = newNode
pre.next = head
return head
N, M, K = map(int, input().split())
head = creatLinkedList(N)
pre = None
cur = head
for i in range(K):
for j in range(M-1):
pre = cur
cur = cur.next
#print(cur.value)
pre.next = cur.next
cur.next = None
cur = pre.next
print(cur.value)
```
<br />
1. 第1 ~ 4行：自訂類別 Node，使用 Node 産生物件時，輸入編號 value，先將下一個物件 self.next 指定為 None。
2. 第6 ~ 14行：自訂函式 creatLinkedList 産生環狀串列，呼叫時輸入數量 n。
1. 第7行：産生環狀串列開頭 head = Node(1)
2. 第8行：環狀串列前一個物件先指定為開頭 pre = head
3. 第9 ～ 12行：使用 for 迴圈産生編別 2、3、…、n 的物件，每次執行 for 迴圈時，先將編號為i新的物件命名為 newNode = Node(i)，再將 newNode 指定為 pre 的下一個物件 pre.next = newNode，最後將 pre 重新定義為 newNode。
4. 第13行：接回開頭處，完成環狀串列。 pre.next = head
5. 第14行：回傳環狀串列的開頭 head
3. 第17行：呼叫 creatLinkedList，産生共有N個物件的環狀串列。
4. 第18行：環狀串列中的前一個物件 pre 暫時指定為 None
5. 第19行：環狀串列中目前的物件 cur 暫時指定為 head
6. 第20 ~ 27行：於 for 迴圈中模擬運作過程
1. 第20行：共有K人出局，此迴圈運作K次。
2. 第21 ~ 24行：炸彈每傳M次就爆炸，此迴圈運作 M-1 次，迴圈結束時 cur 為出局者。如果想要印出出局者，可以移除第26行的註解符號。
3. 第25 ~ 27行：刪除出局者，於環狀串列中跳過 cur，連接到 cur.next。
7. 印出幸運者的編號。
<br /><br />
### 方法4
這個方法的出處為 [http://yuihuang.com/zj-c296/](http://yuihuang.com/zj-c296/)， 適合算數學程度較好的同學，從最後的贏家逆推𠩤來的編號，最後印出時再加1。可以通過 ZeroJudge 的測試，但是最後一筆測資費時 0.2 s，測資數量似乎很大。
```python=
N, M, K = map(int, input().split())
idx = 0
num = N-K
for i in range(1, K+1):
idx = (idx + M) % (num + i)
print(idx+1)
```
<br />
1. 為了方便運算，成員的編號由0開始，最後輸出結果時再加1。
2. 先假設幸運者的編號 $idx_{0} = 0$，最後剩下的人數 $num = N - K$。
3. 第 $K$ 次（最後1次）運作時，參與的人數為 $num + 1$，幸運者原來的編號為 $idx_{k-1} = M \% (num + 1)$。
4. 第 $K-1$ 次（倒數第2次）運作時，參與的人數為 $num + 2$，幸運者原來的編號為 $idx_{k-2} = (idx_{k-1} + M) \% (num + 2)$。
5. 第 $K-2$ 次（倒數第3次）運作時，參與的人數為 $num + 3$，幸運者原來的編號為 $idx_{k-3} = (idx_{k-2} + M) \% (num + 3)$。
6. 若 $i = 1、2、\dots、K$，則第 $K-i+1$ 次（倒數第$i$次）運作時，參與的人數為 $num + i$，幸運者原來的編號為 $idx_{i} = (idx_{i-1} + M) \% (num + i)$。
7. 輸出幸運者的編號，由於題目的編號從1開始，需要將 idx 加1。
<br /><br />
按照同樣的想法，也可以寫成以下這樣，於 ZeroJudge 測試，花費時間為 80 ms，使用記憶體 3.3 MB。
```python=
N, M, K = map(int, input().split())
R = 0
for i in range(N-K+1, N+1): R = (R+M)%i
print(R+1)
```
<br />
如果用 C++ 解題，於 ZeroJudge 測試，花費時間為 8 ms，使用記憶體 332 kB。
```cpp=
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
int N, M, K, R = 0;
cin >> N >> M >> K;
for(int i=N-K+1; i<=N; i++) R = (R+M)%i;
cout << R+1 << endl;
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`C++`、`Python`
Sign in with Wallet
Connect another wallet