URAL 1023 Background 分析

发布时间:2017-1-19 6:09:49 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"URAL 1023 Background 分析",主要涉及到URAL 1023 Background 分析方面的内容,对于URAL 1023 Background 分析感兴趣的同学可以参考一下。

URAL/1023Background   时间限制:2s内存限制:16MB Background Yekaterinburg获得了2032年夏季奥运会的举办权。由于允许俄罗斯(举办国)对竞赛项目进行一些小的修改。现打算修改“Button”这个新项目的规则。规则很简单,在2个对手前有一堆扣子(k个),2人轮流取走扣子,同一时间,某人能取走1至L个扣子。取走最后一个扣子的为胜者。作为奥运会项目,规则应该比通常玩的要难一点。先走者可以设定数K(就是总共有k个扣子),3<=K<=100 000 000.后走者可以设定数 L,2 ≤ L < K Problem 现在要紧的问题是,请你写一个程序,帮助后走者做出抉择。换言之,当给出K后,你的程序能给出数L,使到后走者能获胜。例如, 如果只有3个扣子,后走者把L定为2,有必胜把握。事实上,如果先走者取了1个扣子,那么后走者可以取剩下的2个扣子,后走者胜。如果先走者取了2个扣子,那么后走者取1个,也是后走者胜。 Input 输入只包含一个整数K,扣子的总数。 Output 输出L。每次最多能取走的扣子总数,要求保证后走者必胜。假如有多个答案,输出最小的。如果不存在保证能必胜的L,则输出0。 Sample Input 3 Sample Output 2 Sample Input 908640443 Sample Output 908640442   【其他数据】: 10 ans:4    100 ans:3    17 ans:16    26 ans:12    200 ans:3    14 ans:6 【代码】: #include<stdio.h> int n,ans; int main() { scanf("%d",&n); for(int i=3;i*i<=n;i++) if(n%i==0) { ans=i-1; break; } if(!ans) if(n&1) ans=n-1; else ans=n/2-1; if(ans<2) ans=n-1; printf("%d\n",ans); return 0; //0.953 108 KB } #include<stdio.h> int main() { int i=3,a; scanf("%d",&a); while(a%i!=0) i++; printf("%d",i-1); return 0; } //0.015 108 KB 【分析】:         这是一道经典的博弈的题目         首先我们想如果给定了k,l,那么怎么确定第一个人是不是必胜的,如果是的那他第一次应该取几个?显然是 k mod (l+1)个,如果 k mod (l+1)=0那么显然是必输的。我们这样看,第一个人第一次取走k mod (l+1)后,剩下的button是(l+1)的倍数,这时无论第二个人取几个(设他取i个),第一个下一次都可以取(l+1-i)个,使剩下的button也是(l+1)的倍数,这样第一个人一定能拿到最后一个。       所以如果k mod (l+1)=0       那么第一个人第一次只能取0个,显然是输的。枚举约数的话,我们从1到sqrt(k)枚举就可以了,但是按题意3<=(l+1),我们会忽略掉2这个约数(如果k是偶数),也同时会忽略掉 k div 2这个约数,最后要特殊判断一下。   转载注明出处:http://blog.csdn.net/u011400953  

上一篇:MongoDB常见及生僻的问题总结
下一篇:【秋季养生:红薯防癌抗癌】

相关文章

相关评论