POJ - 1067 取石子游戏（博弈）

比眉伴天荒 2022-05-19 02:25 151阅读 0赞

#                                              取石子游戏 #

### Description ###

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

### Input ###

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

### Output ###

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

### Sample Input ###

2 1
    8 4
    4 7

### Sample Output ###

0
    1
    0

**题意描述：**  
在两堆石子中有两种取法，一是在任意一堆中取任意多石子，二是在两堆中同时取走相同数量的石子，问先取的是否能获胜。

**解题思路：**

看了网上的题解，知道了这种博弈为威佐夫博弈（Wythoff Game），若两堆数量不同，

如将大数存入n小数存入m；如果m=(int)(((sqrt(5.0)+1)/2.0)\*(n-m));则先手必败，其他情况先手必赢；两堆数量相同时也是先手赢。

**错误分析：**  
注意公式中是当所有数运算完再转化为int类型整数，再与m比较。

#include<stdio.h>
    #include<math.h>
    int main()
    {
    	long long n,m,t;
    	while(scanf("%lld%lld",&n,&m)!=EOF)
    	{
    		if(n==m)
    			printf("1\n");
    		else
    		{
    			if(n<m)
    			{
    				t=m;
    				m=n;
    				n=t;
    			}
    			if(m==(int)(((sqrt(5.0)+1)/2.0)*(n-m)))
    				printf("0\n");
    			else
    				printf("1\n");
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关搜索与回溯：取石子游戏

1218：取石子游戏时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4790 通过数: 2208 【题目描述】有两堆石子,两...

深碍√TFBOYSˉ_/ 2024年04月19日 12:11/ 0 赞/ 8 阅读

相关【博弈】牛牛取石子

[D-牛牛取石子\_牛客小白月赛65 (nowcoder.com)][D-_65 _nowcoder.com] 题意： ![43167f0adb9483a2a94ae04f

男娘i/ 2024年03月29日 15:08/ 0 赞/ 8 阅读

相关 51nod 1067 博弈

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

比眉伴天荒/ 2022年08月21日 12:59/ 0 赞/ 132 阅读

相关 HDOJ 2516-取石子游戏

取石子游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

ゞ浴缸里的玫瑰/ 2022年08月20日 04:19/ 0 赞/ 116 阅读

相关 poj 1067 取石子游戏

取石子游戏 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

超、凢脫俗/ 2022年08月03日 14:40/ 0 赞/ 128 阅读

相关 HDU 2516-取石子游戏（斐波那契博弈）

取石子游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

小灰灰/ 2022年07月24日 03:27/ 0 赞/ 112 阅读

相关【数据结构】博弈游戏取石子

\\一、游戏思路：欢迎来到“取石子”游戏世界，这是一个减法游戏。两名对手交替从某给定的总数减去一个数，每个对手只能减去1或者2，谁第一个把总数减到零或者更小的数算谁赢。

你的名字/ 2022年06月06日 09:12/ 0 赞/ 173 阅读

相关 POJ - 1067 取石子游戏（博弈）

取石子游戏 Description 有两堆石子，数量任意，可以不同。游戏开

比眉伴天荒/ 2022年05月19日 02:25/ 0 赞/ 152 阅读

相关 Applese 的取石子游戏（ nim博弈）

链接：[https://ac.nowcoder.com/acm/contest/330/A][https_ac.nowcoder.com_acm_contest_330_A]

蔚落/ 2022年04月23日 08:26/ 0 赞/ 139 阅读

相关取石子游戏

[也许更好的阅读体验][Link 1] \\(\\mathcal\{Description\}\\) ![qsz10914f.png][][![qsz2b35c5.png]

港控/mmm°/ 2021年11月09日 20:04/ 0 赞/ 211 阅读