uva 305 Joseph

思路: 數學+打表
分析:
1 傳統的約瑟夫問題是給定n個人和m，每次數m次把當前這個人踢出局，問最後留下的一個人的編號
2 這一題是前k個人是好人，後面k個是壞人。現在要求最小的m使得沒有一個好人被踢出去的情況下k個壞人都被踢出
3 按照傳統的方法來分析的話，n個人的編號從0~n-1
   第一次  a[1] = (m-1)%n; // 這裡由於人的編號是0~n-1
   第二次  a[2] = (a[1]+m-1)%(n-1);
   第i次     a[i] = (a[i-1]+m-1)%(n-i+1);
   那麼我們可以知道每次的刪除的人的編號，由於k最大14所以我們可以先打表找到1～14的解，然後輸出即可。

代碼:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int solve(int k){
    int pre;
    int tmp = k+1;
    int n = 2*k;
    while(tmp){
        if((tmp-1)%n >= k && (tmp-1)%n < 2*k){
            pre = (tmp-1)%n;
            int i;
            for(i = 2 ; i <= k ; i++){
               int x = (pre+tmp-1)%(n-i+1); 
               if(x < k || x >= 2*k)
                   break;
               else
                   pre = x;
            } 
            if(i == k+1)
                return tmp;
        }
        tmp++;
    }
}

int main(){
    int k , ans[20];
    for(int i = 1 ; i < 15 ; i++)
        ans[i] = solve(i);
    while(scanf("%d" , &k) && k)
        printf("%d\n" , ans[k]);
    return 0;
}