JZOJ.5306【NOIP2017模拟8.18】棋盘游戏

Description

这个游戏上在一个无限大的棋盘上，棋盘上只有一颗棋子在位置（x,y）(x,y>=0)
棋盘的左下角是（0，0）
Amphetamine每次都是第一个移动棋子，然后Amphetamine与Alphago轮流移动。每一轮可以做以下三种中的一种操作：
1）在同一行，将棋子从当前位置向左移动任意格；
2）在同一列，将棋子从当前位置向下移动任意格；
3）将棋子从当前位置向下移动k格再向左移动k格（k为任意正整数，且要满足移动后的棋子仍然在棋盘上）
第一个不能在棋盘上移动的人比赛算输（因为棋子处在（0,0）点）。
共有T个回合（1<=T<=1,000）,每次给出一个新起始点的坐标（x,y）,确定是谁赢。

Input

第1行：一个整数T；
第2到第T+1行：两个用空格隔开的整数x和y.

Output

第1到T行：包含“Amphetamine”或者是“Alphago”，表示谁赢了这轮游戏。

Sample Input

1

1 1

Sample Output

Amphetamine

Data Constraint

对于100% 的数据x,y在int范围内，T<=1000
30%的数据 x,y<=1000
60%的数据 x,y<=100000

威佐夫博弈

$t=\left\lfloor \dfrac {\left( 1+\sqrt {5}\right) \left( y-x\right) } {2}\right\rfloor \left( y>x\right)$

如果t=x则先手必败

否则先手必胜。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 int x,y,t,qwq;

 int main(){

     scanf("%d",&t);

     while (t--){

         scanf("%d%d",&x,&y);

         if (x>y) swap(x,y);

         qwq=floor((+sqrt())/*(y-x));

         if (qwq==x) printf("Alphago\n");

         else printf("Amphetamine\n");

     }

     return ;

 }

神奇的代码

To be continue......

巴特西