Description

Input

Output

Sample Input

3
4
0

Sample Output

5
30

Source

约瑟夫问题的变形，开始对题意就理解了好久，这类题目主要要找到中间的公式；这道题就要知道 当前出局的位置 = （前一个出局的位置+m-1)%(2k-(k-1);

是从0开始数，这就是一个通式；明白了这个公式这个题相当于就做出了一半；这中间还有一个判别的条件，就是如果当前的位置如果<k，说明这种情况就不满足了；

第一种方法：就直接可以对m的值进行枚举，利用判别条件，找出合适的m值；

下面是代码；这种思路好像200ms可以过；

//暴力+枚举
#include <cstdio>
#include <cstring>
int main()
{
    int k;
    int ans[20];//储存当前的位置
    int Joseph[20]={0}; //储存符合条件的m的值
    for(k=1;k<14;k++)
    {
        int m=1;
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=k;i++)
        {
            ans[i]=(ans[i-1]+m-1)%(2*k-i+1); //递推公式
            if(ans[i]<k)
            {
                i=0;
                m++;
            }
        }
        Joseph[k]=m;
    }
  while(scanf("%d",&k)&&k!=0)
   {
       printf("%d\n",Joseph[k]);
   }
   return 0;
}

//直接枚举 0ms
#include <cstdio>
#include <cstring>
int main()
{
    int k;
  int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
  while(scanf("%d",&k)&&k!=0)
   {
       printf("%d\n",Joseph[k]);
   }
   return 0;
}

题目中的隐含条件；只剩下一个坏人的时候，下一个报数的人要么是第1个人，要么是第k+1个人；所以间隔就是m=s*(k+1)或者是 m=s*(k+1)+1;

粗略的证明一下，参考别人的：（这里我也还有点没懂）

仅剩一个坏人，圈长为k+1；设下一个报数人为第一个人时的时间间隔为m1；下一个报数人为第k+1个人时的时间间隔为m2；

由 （1+m1）%（k+1）=1 得出 m1= s*(k+1);

   (k+1+m2)%(k+1)=1  得出 m2=s*(k+1)+1;

这样我们就可以对m的枚举优化剪枝，m是（k+1）的倍数或者是他的倍数+1；

#include <cstdio>
#include <cstring>
bool Joseph(int k,int m)
{
    int n=2*k,x=0;
    while(n>k)
    {
        x=(x+m-1)%n;//递推公式，算出当前出局的位置
        if(x<k) //判别条件
            return false;
        n--;
    }
    return true;
}
int main()
{
    int k;
    int result[20]={0};
    for(k=1;k<14;k++)
    {
        for(int i=k+1;;i+=k+1) //对m枚举进行优化
        {
            if(Joseph(k,i)) //m是k+1的倍数或者倍数+1
            {
                result[k]=i;
                break;
            }
            else if(Joseph(k,i+1))
            {
                result[k]=i+1;
                break;
            }
        }
    }
    while(scanf("%d",&k)&&k)
    {
        printf("%d\n",result[k]);
    }
}

poj 1012 Joseph (约瑟夫问题）