POJ 1012 Joseph

传送门：https://vjudge.net/problem/11573/origin

The Joseph’s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input
The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.
Output
The output file will consist of separate lines containing m corresponding to k in the input file.
Sample Input
3
4
0
Sample Output
5
30

题意

  有 k 个 goodguy（编号 1 ~ k），k 个badguy（编号 k+1 ~ 2k），按编号坐成一个环，依次报数，报到 m 的人出列，重复过程。求解最小的 m，使得所有的 badguy 比 goodguy 先出列。

解决算法

我们这里假设环的编号是从0开始。
注意观察到报数 m 具有延续性，对于 n 个人来说，第一轮约瑟夫环淘汰了一个人后，剩下的 n-1 个人其实有组成了一个新的约瑟夫环，区别在于两个约瑟夫环中的成员编号不同。因此我们可以理解为这里需要解决的是不同编号序列之间的一个映射关系，即将第 i+1 轮种淘汰的人的编号映射到第 i 轮中对应的编号序列。先给出状态转移方程：

• $ans[0]=0（i==1）$
• $ans[i]=(ans[i-1]+m-1)/(n-i+1)（i>=1）$

详细推导，可以自己推一下。
然后的话，我们知道 m 一定是 k 到 2k-1 的倍数（从 0 开始编号的话），所以少一点遍历。
打表的话：

jp[] = {
    0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,13482720}

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f3f;
const double eps = 1e-6;
const int maxn = 10010;
int jp[20];
int main(void)
{
    
    int n,m,k;
    while(~scanf("%d",&k)&&k){
    
        if(jp[k]){
    
            printf("%d\n",jp[k]);
            continue;
        }
        int ans[20]={
    0};
        n = 2*k;
        m = k;
        ans[0] = 0;
        for(int i=1;i<=k;i++){
    
            ans[i] = (ans[i-1]+m-1)%(n-i+1);
            if(ans[i]<k){
    
                if(m==n)    m = m+k;
                else   m++;
                i = 0;
            }
        }
        jp[k] = m;
        printf("%d\n",m);
    }
    return 0;
}