[ 登录注册 ]

语言

CSDN高校俱乐部第二届战神杯第二题题解

2017-07-14 10:37:46 admin 返回上一页

标签:style   class   blog   code   数据   2014   

两个人玩一个数字游戏,给定两个正整数AB,两个人轮流从一个数中减去另外一个数的正数倍,要保证结果非负,

首先得到0的人获胜。例如:30 8经过一步操作可以变为22 8 或者14 8 或者 6 8。两个人都足够聪明。

输入格式:

多组数据,每组数据占一行是两个空格分隔的正整数(在32位整书范围内)

输出格式:

每组数据一行,输出是第一个人赢,还是第二个人赢。

输入:

3 5

4 5

输出:

1

2

思路:如果你知道连分数,这题就是水题一道了。(记得某神说,菜鸟做完一题总是说这题很简单!没错,我就是菜鸟)

先手必败当且仅当(sqrt(5)-1)/2=1/[1;111...]<a/b<[1;111...]=(sqrt(5)+1)/2.

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;double lt=(sqrt(5.0)-1)/2.0;double rt=(sqrt(5.0)+1)/2.0;bool isWin(int aint b){double tmp=(a+0.0)/b;if(lt<tmp&&tmp<rt){return false;}return true;}int main(){int ab;while(cin>>a>>b){if(isWin(ab)){puts("1");}else{puts("2");}}return 0;}



CSDN高校俱乐部第二届战神杯第二题题解布布扣bubuko.com

CSDN高校俱乐部第二届战神杯第二题题解

标签:style   class   blog   code   数据   2014   


文章来源:http://www.bozhiyue.com/yuyan/2017/0714/1484289.html
返回上一页    返回分类 上一篇:   下一篇:
相关