http://poj.org/problem?id=1012
早上去图书馆复习苦逼的复习。。。。万恶的数逻。T T我还要自我安慰的说复习完了奖励回来刷水题~
10点多的时候外面校运会大吼撑杆跳的那个。等到解说说要破纪录了，哥哥我果断收拾东西，跑去看，结果即将到的时候说跳过去了记录破了T T哭瞎了。
---------------------------------------------------大家好，我是分割线---------------------------------------------------
暴力的话肯定悲剧。好吧，不会做。搜题解的。（说好的奖励刷水题QAQ）
首先说一下约瑟夫问题：N个人围成一圈，从第一个开始报数，第m个将被杀掉，最后剩下一个，其余人都将被杀掉。
题目大意：
给定一个数k，前面k个人是好人，后面k个人是坏人，要求找到最少的报数号码m，使得在好人被杀之前坏人全部死亡。
设有n个人（0,...,n-1），数m，则第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; f(i) 表示当前子序列中要退出的那个人（当前序列编号为0~(n-i));
拿个例子说：K=4,M=30;
f(0)=0;
f(1)=(f(0)+30-1)%8=5; 序列（0,1,2,3,4,5,6,7）中的5
f(2)=(f(1)+30-1)%7=6; 序列（0,1,2,3,4,6,7）中的7
f(3)=(f(2)+30-1)%6=5; 序列（0,1,2,3,4,6）中的6
f(4)=(f(3)+30-1)%5=4; 序列（0,1,2,3,4）中的4
.......
依据题意，前K个退出的人必定是后K个人，所以只要前k轮中只要有一次f(i)<k则此m不符合题意。
可以打表直接过的。
#include<cstdio>
int ans[29]={0};
int joseph[15];
int main()
{
int k;
while(scanf("%d",&k),k)
{
if(!joseph[k])
{
int n= k<<1;
ans[0]=0;
int m=1;
for(int i=1;i<=k;i++)
{
ans[i]=( ans[i-1]+m-1) %(n-i+1);
if(ans[i] <k)
{
m++;
i=0;
}
}
joseph[k]=m;
}
printf("%d\n",joseph[k]);
}
}
打表。
#include<cstdio>
int joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
int main()
{
int k;
while(scanf("%d",&k),k)
{
printf("%d\n",joseph[k]);
}
}