约瑟夫问题,稍有变化
n个人站成一圈,从某个人开始数数,每次数到m的人就被杀掉,然后下一个人重新开始数,直到最后只剩一个人。
现在有一圈人,k个好人站在一起,k个坏人站在一起。从第一个好人开始数数。
你要确定一个最小的m,使得在第一个好人被杀死前,k个坏人先被杀死。
Input
一个k,0<k<14
Output
一个m
[解决办法]
写了一个,以为他只有13个输入,但是被阴了,他居然把输入过的数重复输入,导致我超时了,于是建表
#include <stdio.h>
int main()
{
int k;
bool flag;
long i,j,m,n,t,r[16];
for(k=1;k<14;k++)
{
i=0;
while(1)
{
for(j=k+1;j<=2*k;j++)
{
m=2*k*i+j;
flag=true;
for(n=1,t=1;n<=k;n++)
{
t=(t+m-1)%(2*k-n+1);
if(t==0) t=2*k-n+1;
if(t<=k&&t>=1)
{
flag=false;
break;
}
}
if(flag) goto end;
}
i++;
}
end: r[k]=m;
}
while(scanf("%d",&k)==1&&k)
{
printf("%ld\n",r[k]);
}
return 0;
}