ZeroJudge 解題筆記：c083. 00130 - Roman Roulette

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


ZeroJudge 題目連結：c083. 00130 - Roman Roulette

解題想法

這題的題目敘述很怪，試了很多種排法才弄懂題目的意思。為了簡化問題，我將人排成一列，順時鐘方向是向右，如果到了最後一位就從最左邊開始算。計算規則如下：

1. 首先是題目要找的起點位置，在計算第一個受害者的位置時，是從起點的左邊那個人開始向右算 k 個人，不是從起點開始算。
2. 計算埋葬者原來的位置時，是從受害者左邊那個人開始向右算 k 個人，將埋葬者的位置移動到受害者的位置。
3. 計算下一個受害者的位置時，是從前一個受害者，也就是埋葬者所在位置左邊那個人開始向右算 k 個人。
4. 如果 1 號死亡，可以中止迴圈，再找下一個起點。
5. 如果存活人數剩下一個，而且這個人是 1 號，找到答案，回傳起點位置。

以範例測資 $n = 5, k = 2, i = 1$ 為例，起始及每一輪的狀態如下

起始: [1, 2, 3, 4, 5]
第1輪: 起點編號 5, 受害者編號 2, 埋葬者編號 4, 目前存活的人 [1, 4, 3, 5]
第2輪: 起點編號 4, 受害者編號 5, 埋葬者編號 4, 目前存活的人 [1,  3, 4]
第3輪: 起點編號 4, 受害者編號 3, 埋葬者編號 1, 目前存活的人 [1, 4]
第4輪: 起點編號 1, 受害者編號 1, 目前存活的人 [4]

Python 程式碼

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

import sys

def solve(n, k):  # 用串列模擬過程求解
    for i in range(1, n+1):  # 依序測試起點編號 1 ~ n
        persons = [j for j in range(1, n+1)]  # 編號 1 ~ n 的人
        pos, m = (i-2+n)%n, n  # 起點位置其實是 i 的左側，轉成索引值再減 1；存活人數 m
        alive = True  # 1 號是否存活
        while m > 1 and alive:  # 如果 m 大於 1 且 1 號還活著，繼續執行
            vpos = (pos+k)%m  # 受害者索引值
            victim = persons.pop(vpos)  # 從 persons 移除受害者
            m -= 1  # 存活人數減 1
            if victim == 1: alive = False  # 如果 1 號死亡，alive 改成 False
            if m == 1: break  # 如果 m 等於 1，中止迴圈
            bpos = (vpos-1+k)%m  # 埋葬者索引值
            burier = persons.pop(bpos)  # 從 persons 移除埋葬者
            if bpos < vpos:  # 如果埋葬者在受害者左側
                persons.insert(vpos-1, burier)  # vpos 減 1，於 persons 插入埋葬者
                pos = (vpos-1+m)%m  # 更新下一輪的起點索引值
            else:  # 如果埋葬者在受害者右側
                persons.insert(vpos, burier)  # 於 persons 插入埋葬者
                pos = (vpos+m)%m  # 更新下一輪的起點索引值
        if alive: return i  # 如果 1 號存活，回傳 i
    return -1  # 無解，回傳 -1，理論上不會用到

for line in sys.stdin:
    n, k = map(int, line.split())
    if n == 0 and k == 0: break
    print(solve(n, k))

C++ 程式碼

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

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

int solve(int n, int k) {  // 用陣列模擬過程求解
    for(int i=1; i<=n; i++) {  // 依序測試起點編號 1 ~ n
        vector<int> persons (n);  // 編號 1 ~ n 的人
        for(int j=0; j<n; j++) persons[j] = j+1;
        int pos = (i-2+n)%n, m = n;  // 起點位置其實是 i 的左側，轉成索引值再減 1；存活人數 m
        bool alive = true;  // 1 號是否存活
        while(m > 1 && alive) {  // 如果 m 大於 1 且 1 號還活著，繼續執行
            int vpos = (pos+k)%m;  // 受害者索引值
            int victim = persons[vpos];  // 從 persons 移除受害者
            persons.erase(persons.begin()+vpos);
            m--;  // 存活人數減 1
            if (victim == 1) alive = false;  // 如果 1 號死亡，alive 改成 False
            if (m == 1) break;  // 如果 m 等於 1，中止迴圈
            int bpos = (vpos-1+k)%m;  // 埋葬者索引值
            int burier = persons[bpos];  // 從 persons 移除埋葬者
            persons.erase(persons.begin()+bpos);
            if (bpos < vpos) {  // 如果埋葬者在受害者左側
                persons.insert(persons.begin()+vpos-1, burier);  // vpos 減 1，於 persons 插入埋葬者
                pos = (vpos-1+m)%m;  // 更新下一輪的起點索引值
            } else {  // 如果埋葬者在受害者右側
                persons.insert(persons.begin()+vpos, burier);  // 於 persons 插入埋葬者
                pos = (vpos+m)%m;  // 更新下一輪的起點索引值
            }
        }
        if (alive) return i;  // 如果 1 號存活，回傳 i
    }
    return -1;  // 無解，回傳 -1，理論上不會用到
}

int main() {
    int n, k;
    while(scanf("%d %d", &n, &k) != EOF) {
        if (n == 0 && k == 0) break;
        printf("%d\n", solve(n, k));
    }
    return 0;
}