ZeroJudge 解題筆記：c086. 00402 - M*A*S*H

作者：王一哲
日期：2026年2月22日


ZeroJudge 題目連結：c086. 00402 - M*A*S*H

解題想法

很像約瑟夫環的題目，但是測資不大，直接模擬淘汰的過程即可。

Python 程式碼

使用時間約為 7 ms，記憶體約為 3 MB，通過測試。

import sys

ca = 0  # 第幾筆測資
for line in sys.stdin:
    ca += 1  # 加1
    if ca > 1: print()  # 如果不是第1筆測資，換行
    arr = list(map(int, line.split()))  # 讀取一行資料
    n, x = arr[0], arr[1]  # n 個人參加，x 個人可以放假
    persons = [i for i in range(1, n+1)]  # 産生 1 ~ n 的編號
    for k in arr[2:]:  # 依序讀取 20 張牌的數字
        if n == x: break  # 如果剩下 x 個人，中止迴圈
        idx = k-1  # 淘汰者的索引值，初始值為 k-1
        while n > x and idx < n:  # 如果人數大於 x 而且 idx 還沒有出界
            persons.pop(idx)  # 淘汰索引值為 idx 的人
            n -= 1  # 人數減 1
            idx += k-1  # 下一個索引值加 k-1，因為淘汰一個人，不是加 k
    print(f"Selection #{ca:d}")  # 印出答案
    print(*persons)

使用時間約為 8 ms，記憶體約為 3 MB，通過測試。

import sys

result = []
data = sys.stdin.read().split()
ptr = 0
ca = 0  # 第幾筆測資
while ptr < len(data):
    ca += 1  # 加1
    if ca > 1: result.append("\n")  # 如果不是第1筆測資，換行
    n = int(data[ptr])  # n 個人參加
    x = int(data[ptr+1])  # x 個人可以放假
    ptr += 2
    persons = list(range(1, n+1))  # 産生 1 ~ n 的編號
    cards = list(map(int, data[ptr:ptr+20]))
    ptr += 20
    for k in cards:  # 依序讀取 20 張牌的數字
        if n == x: break  # 如果剩下 x 個人，中止迴圈
        idx = k-1  # 淘汰者的索引值，初始值為 k-1
        while n > x and idx < n:  # 如果人數大於 x 而且 idx 還沒有出界
            persons.pop(idx)  # 淘汰索引值為 idx 的人
            n -= 1  # 人數減 1
            idx += k-1  # 下一個索引值加 k-1，因為淘汰一個人，不是加 k
    result.append(f"Selection #{ca:d}\n")  # 印出答案
    res = " ".join(map(str, persons))
    result.append(f"{res}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 284 kB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int ca = 0, n, x, cards[20];  // 第幾筆測資，n 個人參加，x 個人可以放假，20 張牌
    while(scanf("%d %d", &n, &x) != EOF) {
        ca++;  // 加1
        if (ca > 1) puts("");  // 如果不是第1筆測資，換行
        for(int i=0; i<20; i++) scanf("%d", &cards[i]);
        vector<int> persons (n);  // 産生 1 ~ n 的編號
        for(int i=0; i<n; i++) persons[i] = i+1;
        for(int i=0; i<20; i++) {  // 依序讀取 20 張牌的數字
            int k = cards[i];
            if (n == x) break;  // 如果剩下 x 個人，中止迴圈
            int idx = k-1;  // 淘汰者的索引值，初始值為 k-1
            while(n > x && idx < n) {  // 如果人數大於 x 而且 idx 還沒有出界
                persons.erase(persons.begin()+idx);  // 淘汰索引值為 idx 的人
                n--;  // 人數減 1
                idx += k-1;  // 下一個索引值加 k-1，因為淘汰一個人，不是加 k
            }
        }
        printf("Selection #%d\n", ca);  // 印出答案
        for(int i=0; i<(int)persons.size()-1; i++) printf("%d ", persons[i]);
        printf("%d\n", persons.back());
    }
    return 0;
}