# 新疆大学 ACM-ICPC 程序设计竞赛五月月赛G chess（威佐夫博弈）

## chess

• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 32768K，其他语言65536K
• 64bit IO Format: %lld

### 题目描述

A single chess queen is placed somewhere on a grid of 10000*10000 squares.Lao Wang and Xiao Ren ready to play a game The rules are player can move the queen towards the lower left corner of the grid: south, west, or southwest, any number of steps. The winner is the player who moves the queen into the southwest corner.If you let the old Xiao Ren first chess .Suppose they will use the best strategy who will win the game?

### 输入描述

The input will consist of a series of pairs of integers a and b, Indicates the distance from the west boundary and the distance from the south boundary.

### 输出描述

For each pair of input integers a and b you should output the winner's name in one line;

### 输入

1 2
3 5
1 1
3 2

### 输出

Lao Wang
Lao Wang
Xiao Ren
Xiao Ren

### 链接

https://www.nowcoder.com/acm/contest/116/G

### 代码

• 运行时间： 46 ms
• 占用内存：2656K
• 代码长度：414
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
if (n > m)
swap(n, m);
int tmp = floor((m-n) * (1+sqrt(5.0)) / 2.0); // 威佐夫博弈
if (tmp == n)
printf("Lao Wang\n");
else
printf("Xiao Ren\n");
}
return 0;
}

### 一. 巴什博奕(Bash Game)

A和B一块报数，每人每次报最少1个，最多报4个，看谁先报到30。这应该是最古老的关于巴什博奕的游戏了吧。

#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
if(n%(m+1)==0)  cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
return 0;
}  

### 二. 威佐夫博弈(Wythoff Game)

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n1,n2,temp;
while(cin>>n1>>n2)
{
if(n1>n2)  swap(n1,n2);
temp=floor((n2-n1)*(1+sqrt(5.0))/2.0);
if(temp==n1) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}  

### 三. 尼姆博弈(Nimm Game)

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n,ans,temp;
while(cin>>n)
{
temp=0;
for(int i=0;i<n;i++)
{
cin>>ans;
temp^=ans;
}
if(temp==0)  cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
}
return 0;
}  

### 四. 斐波那契博弈

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N = 55;
int f[N];
void Init()
{
f[0] = f[1] = 1;
for(int i=2;i<N;i++)
f[i] = f[i-1] + f[i-2];
}
int main()
{
Init();
int n;
while(cin>>n)
{
if(n == 0) break;
bool flag = 0;
for(int i=0;i<N;i++)
{
if(f[i] == n)
{
flag = 1;
break;
}
}
if(flag) puts("Second win");
else     puts("First win");
}
return 0;
}

The end.
2018-05-11 星期五