(原创)
有一天 pb和zs玩游戏 你需要帮zs求出每局的胜败情况
游戏规则是这样的: 每次一个人可以对给出的数进行分割,将其割成两个非零自然数,之后由另一个人选择留下两个数中的其中一个;之后由另一个人进行分割这个剩下的数,重复步骤……
当一个人无法对数进行分割的时候游戏结束,另一个人获胜
现在要你求出N次游戏的胜败
每局由pb先进行分割,如果pb赢输出"pb wins" 如果zs赢输出"zs wins"
注:双方都是绝顶聪明的
输入格式:
第一行一个数N,表示数据组数
之后N行,每行一个数M,表示每局初始的数
输出格式:
共N行,每行一串字符 表示游戏结果
输入样例#1:
5
1
3
7
20
5
输出样例#1:
zs wins
zs wins
zs wins
pb wins
zs wins
1<N<50
1<=m<=1000000000
看样例,推算法
简单的奇偶判断
归纳证明:n=1时先手必输;
n=2时2分解成1+1;后手无论选哪个都必输。
假设k<=n时奇数先手必输,偶数先手必胜。
n+1为奇数时,先手只能把n+1分成不超过n的一个奇数一个偶数,机智过人的后手一定会选择偶数来保证自己不败。
n+1为偶数时,机智过人的先手一定会把n+1分解成两个奇数,后手不得不选择奇数从而走向自爆。
到这里就证明了这个问题
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdio>
4 #include<cmath>
5 using namespace std;
6 int read(int & n)
7 {
8 char c='-';int x=0;
9 while(c<'0'||c>'9')c=getchar();
10 while(c>='0'&&c<='9')
11 {
12 x=x*10+(c-48);
13 c=getchar();
14 }
15 n=x;
16 }
17 int main()
18 {
19 int n;
20 read(n);
21 for(int i=1;i<=n;i++)
22 {
23 long long p;
24 cin>>p;
25 if(p%2==0)
26 printf("pb wins\n");
27 else
28 printf("zs wins\n");
29 }
30 return 0;
31 }