Power OJ 1004: 分花生游戏 (博弈论)

我就是我 2021-09-28 04:44 381阅读 0赞

# [PowerOJ 1004: 分花生游戏 (博弈论)][PowerOJ 1004_ _] #

## Description ##

> 4月6日，我校Nicholas代表队做火车前往湖北武汉大学参加“百度杯”第二届华中北区ACM程序设计邀请赛，在火车上老师和队员们觉得要找点事情来做，于是小谭（谭老师）就抓了一大包花生出来，让大家玩一个分花生的游戏，游戏规则如下：  
> 桌子上放着两堆花生，Player1和Player2轮流对这些花生进行操作。在每一次操作中，操作者需要吃掉其中一堆花生，并且把另一堆花生分成两堆（可以不相等）留给对方操作。游戏如此进行下去，花生数会越来越少，最后必将出现这样一种情况：某人吃掉一堆花生后发现另一堆里只剩一颗花生不能再分了。游戏规定此时该操作者吃掉最后这一颗花生从而取胜。  
> 起初Nicholas的队员轮流挑战小谭，可是全部都很遗憾的落败了，旁边的杨老师实在看不下去了便提醒队员们这个游戏是不公平的，对于任意一种初始状态，总有一方有必胜策略。所谓有必胜策略是指，无论对方如何操作，自己总有办法取胜。  
> 现在将进行10次游戏，每一次游戏中总是小谭先进行操作。现在你的任务就是帮助Nicholas的队员们设计一个程序来判断每一次游戏中Nicholas的队员是否有必胜策略。（假设小谭和队员们都是用最优的方式在进行操作）。

## Input ##

> 输入数据一共10行，每行有两个用空格隔开的正整数m,n( 0 < m,n < 100000  
> )，表示一次游戏开始时桌子上两堆糖果分别有多少个。

## Output ##

> 输出十行字符串。这些字符串只能是“Yes”或“No”，它们表示对应的十行输入数据Nicholas的队员是否有必胜策略。请注意大小写。

## Sample Input ##

> 1 1  
> 1 2  
> 1 3  
> 1 4  
> 1 5  
> 2 1  
> 2 2  
> 2 3  
> 2 4  
> 2 5

## Sample Output ##

> No  
> No  
> No  
> No  
> No  
> No  
> Yes  
> Yes  
> No  
> No

首先我们来分析一下，不妨设小谭先取第一堆，然后对第二堆的分法进行分析  
（第二堆为任意数 0<x<100000）  
当第二堆为1时，队员必败  
当第二堆为2时，小谭分为1 1，队员必胜  
当第二堆为3时，小谭分为1 2，队员必胜  
当第二堆为4时，小谭分为2 2，（不分为1 3的原因是双方均选择最优的方式在操作），队员拿走第一堆，队员分为1 1，队员必败  
当第二堆为5时，小谭分为2 3，队员拿走2或者3都会分为1 x模型，队员必败  
当第二堆为6时，小谭分为3 3，队员拿走第一堆，队员分为1 x模型，队员必败  
当第二堆为7时，小谭分为2 5时，队员拿走2，分为2 3，与之前的第二堆为5时相似，队员必胜，小谭分为3 4时，队员拿走3，分为2 2，与之前的第二堆为4时相似，队员必胜  
当第二堆为8时，小谭分为2 6时，队员拿走2，分为3 3，与之前的第二堆为6时相似，队员必胜，小谭分为3 5时，队员拿走3，分为2 3，与之前的第二堆为5时相似，队员必胜,小谭分为4 4时，队员拿走4，分为2 2，与之前的第二堆为4时类似，队员必胜。  
以此规律类推第二堆为2 3 7 8 12 13 17 18…等数据时，队员是必胜局面。  
然后就发现规律：存在某堆减去1再mod 5后等于0,3,4则必败，否则必胜（对于队员）  
那么，只要这两堆任意一堆满足该规律，队员必败。  
样例代码如下：

#include<stdio.h>
    int main()
    { 
        int m,n;
        while(scanf("%d%d",&m,&n)!=EOF)
        { 
        	if((m-1)%5==0||(m-1)%5==3||(m-1)%5==4||(n-1)%5==0||(n-1)%5==3||(n-1)%5==4)
        	printf("No\n");
        	else
        	printf("Yes\n");
        }
        return 0;
    }

[PowerOJ 1004_ _]: https://www.oj.swust.edu.cn/problem/show/1004