ACM 經典題 Josephus 變體：POJ 1012 / UVa 305 打表解法

題目：有 k 個好人、k 個壞人圍成圈 (前 k 個好人)，每隔 m-1 人處決一人，求最小 m 使得前 k 個被處決的全是壞人。0 < k < 14。

核心觀察

• k ≤ 13，搜索空間極小，且測試用例固定，**打表 (查表法)** 是工程上最優解。
• 預計算或離線搜索得到所有 k 對應的最小 m，代碼中直接查表輸出，O(1) 通過。

已知答案表 (k=1..13)

k :  1   2   3    4     5      6       7        8         9          10
m :  2   7   5   30   169    441    1872     7632     1740       93313

k :    11       12         13
m :  459901  1358657    2504881

AC 代碼 (C)

#include 

int main() {
    int ans[14] = {
        0,          // 0 佔位
        2, 7, 5, 30, 169, 441, 1872, 7632,
        1740, 93313, 459901, 1358657, 2504881
    };
    int k;
    while (scanf("%d", &k) == 1 && k != 0) {
        printf("%d\n", ans[k]);
    }
    return 0;
}

離線搜索原理 (供理解)

// 模擬過程：對候選 m，模擬約瑟夫環，檢查前 k 個出局者是否全 ≥ k+1 (壞人編號)
bool check(int k, int m) {
    int total = 2*k;
    int pos = 0; // 當前位置 (0-based)
    for (int i = 0; i < k; ++i) { // 需淘汰 k 個壞人
        pos = (pos + m - 1) % total;
        if (pos < k) return false; // 淘汰了好人
        total--; // 壞人減少
        if (pos == total) pos = 0; // 環狀調整
    }
    return true;
}
// 對每個 k 從 k+1 開始枚舉 m，找到第一個 check 通過的即為答案

離線搜索對 k=13 需遍歷至 250 萬，單次運行秒級，適合預計算生成表。

總結

• 競賽中遇到小範圍、固定答案問題，**打表優於算法**。
• 約瑟夫問題變體核心是模擬環狀刪除，索引更新公式 (pos + m - 1) % remain。
• 注意輸入以 0 結束，多行獨立測試用例。