取石子游戏

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7192    Accepted Submission(s): 4313

Problem Description
1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".
 
Input
输入有多组.每组第1行是2<=n<2^31. n=0退出.
 
Output
先取者负输出"Second win". 先取者胜输出"First win". 
参看Sample Output.
 
Sample Input
2
13
10000
0
 
Sample Output
Second win
Second win
First win
 
Source
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  2509 2512 1536 2510 1907 
 
寻找规律可以知道,必败的情况下都是斐波那契数,所以做一匹配就可以了,使用离线和二分法搜索来提高效率。

 #include<bits/stdc++.h>
using namespace std; long long fs[]; void init() {
fs[] = ;
fs[] = ; for(int i = ; i <= ;i ++) {
fs[i] = fs[i-] + fs[i-];
}
} bool find(long long n) {
int l = ;
int r = ;
int mid = (l+r) >> ; // (l+r)/2
while(l <= r) {
if(fs[mid] == n) return true;
else if(fs[mid] < n) l = mid + ;
else r = mid - ;
mid = (l+r) >> ;
}
return false;
} int main() { init();
long long n;
while(~scanf("%lld",&n)&&n) {
if(find(n)) puts("Second win");
else puts("First win");
}
return ;
}
 

最新文章

  1. sql server 常用的扩展存储过程
  2. win php nginx 配置小细节
  3. Java对MySQL数据库进行连接、查询和修改【转载】
  4. MINA源码阅读之ACP
  5. Tomcat的server.xml(中文版)
  6. substr(dirname(__FILE__))
  7. Hibernate由model类自动同步数据库表结构
  8. 浏览器中显示PPT的展示效果
  9. 2019-04-16 SpringMVC 学习笔记
  10. 在Kubernetes中部署GlusterFS+Heketi
  11. Linux学习笔记之Centos7安装GNOME桌面环境
  12. [翻译] EnterTheMatrix
  13. 使用开源库 EasyTimeline 操作定时器 NSTimer
  14. eAccelerator 配置参数详解
  15. phpcms开启在线编辑模版 方法
  16. Mycat实战之离散分片
  17. 【C#】 RBAC 权限框架
  18. Selenium3 Python3 Web自动化测试从基础到项目实战之二浏览器的不同设置
  19. C#复习总结6 (需要进一步复习)
  20. Oracle imp exp命令具体解释

热门文章

  1. [洛谷P1196][NOI2002]银河英雄传说 - 带偏移量的并查集(1)
  2. Spark:将RDD[List[String,List[Person]]]中的List[Person]通过spark api保存为hdfs文件时一直出现not serializable task,没办法找到&quot;spark自定义Kryo序列化输入输出API&quot;
  3. 框架学习之Struts2(三)---OGNL和值栈
  4. 目标检测算法YOLO算法介绍
  5. tkinter打招呼
  6. MySQL &#183; 引擎特性 &#183; InnoDB 数据页解析
  7. Linear Regression with Scikit Learn
  8. 洛谷P2405 non天平
  9. bzoj 2555: SubString
  10. ●UOJ 131 [NOI2015] 品酒大会