OJ4TH|Let's play a game

时间限制: 1000 ms 内存限制: 65536 kb

总通过人数: 292 总提交人数: 351

题目描述

这是一个古老而无聊的游戏，这是一个欧几里得躺枪的游戏。

Nova君和LaoWang决定一分胜负。给定两个正整数a,b。Nova君和LaoWang轮流从中将较大的数字减去较小数字的整数倍（1倍，2倍等等）。并且保证每次减完不会出现负数的情况。由Nova君先手。最终在自己回合将其中一个数变为0的一放获胜。两个人智商都还行，都会采取最优策略，谁会赢呢？

输入

多组测试数据。对于每组测试数据，给出两个数字a和b（保证Int范围内）

输出

对于每组数据，输出获胜者的名字。

输入样例

34 12
15 24

输出样例

Nova
LaoWang

题目分析

简单的博弈论。分为必胜态和必败态。pan(a,b)表示如果当前玩家拿到a,b，会赢还是会输。

我们把状态分为必胜态和必败态。

1.如果当前数字中有一个是0，那么当前状态为必败态（上一轮把一个数字变成0的人赢了）。

2.如果没有0，那么如果当前状态可以转移到必败态，则当前状态为必胜态。否则当前状态为必败态。

代码

代码思路不难。但不知为何总是超时。逼得我把cin、cout全换掉了，甚至交换ab都用上了位运算……最后是把while循环改成了for循环，秒过。

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;

int pan(int a,int b)
{
    int x=a,y=b;
    if (x<y) { x=x^y; y=x^y; x=x^y; }
    if (y==0) return 0;
    for (int i=x/y; i>0; i--)
        if (pan(x-i*y,y)==0) return 1;
    return 0;
}

int main()
{
    int a,b;
    while (scanf("%d %d",&a,&b)!=EOF)
    {
        if (pan(a,b)==1) printf("Nova
");
            else printf("LaoWang
");
    }
    return 0;
}