早上去图书馆复习苦逼的复习。。。。万恶的数逻。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不符合题意。
可以打表直接过的。
#includeint 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]
打表。
#includeint 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]); }}