POJ 1012 Joseph：約瑟夫問題變體求最小步長

題目簡介

2k 個人圍圈，前 k 個好人（1..k），後 k 個壞人（k+1..2k）。每次數 m 淘汰一人。求最小 m 使得所有壞人在任何好人被淘汰前被淘汰完。k < 14。

解題思路

模擬淘汰過程，關鍵在於編號重排：淘汰一個壞人後，剩餘壞人前移填補編號，好人編號始終 1..k。因此只需維護剩餘總人數 rest 和當前淘汰位置 kill。公式：kill = (kill + m - 1) % rest（0 視為 rest）。若淘汰位置 > k（或 ==0 視為 rest，即最後一個），則淘汰壞人；否則淘汰好人，m 失效。枚舉 m 從 k+1 開始，直到找到能淘汰 k 個壞人的 m。

代碼實現

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

int main() {
    int k;
    while (cin >> k && k) {
        int n = 2*k;
        for (int m = k+1; ; m++) {
            int rest = n, kill = 1, bad = 0;
            while (bad < k) {
                kill = (kill + m - 1) % rest;
                if (kill == 0) kill = rest;
                if (kill > k) { bad++; rest--; }
                else break; // 淘汰好人，m 無效
            }
            if (bad == k) { cout << m << endl; break; }
        }
    }
    return 0;
}

打表優化

k ≤ 13，可預計算所有答案存入數組直接輸出：

k: 1 2 3 4 5 6 7 8 9 10 11 12 13
m: 2 7 5 30 169 441 1872 7632 1740 93313 459901 1358657 2504881