POJ1067 取石子游戏(博弈论)

2024-08-25 08:08

本文主要是介绍POJ1067 取石子游戏(博弈论),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

取石子游戏

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 36633 Accepted: 12396

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):

具体详细证明看转载的博客,在我博客中有,各种常见博弈的解题方法。

1)给你一个局面,让你求是先手输赢。

有了上面的分析,那么这个问题应该不难解决。首先求出差值,差值 * 1.618 == 最小值 的话后手赢,否则先手赢。(注意这里的1.618最好是用上面式子计算出来的,否则精

度要求高的题目会错)

 

2)给你一个局面,让你求先手输赢,假设先手赢的话输出他第一次的取法。

       首先讨论在两边同时取的情况,很明显两边同时取的话,不论怎样取他的差值是不会变的,那么我们可以根据差值计算出其中的小的值,然后加上差值就是大的一个值,当

然能取的条件是求出的最小的值不能大于其中小的一堆的石子数目。

      加入在一堆中取的话,可以取任意一堆,那么其差值也是不定的,但是我们可以枚举差值,差值范围是0 --- 大的石子数目,然后根据上面的理论判断满足条件的话就是一种合理的取法。


AC代码:

#include<iostream>
#include<cmath>
using namespace std;
int main()
{int m,n;while(cin>>m>>n){if(m < n){m ^= n;n ^= m;m ^= n;}int k = m - n;if((int)(k * (sqrt(5 * 1.0) + 1) / 2) == n){cout<<"0"<<endl;}else{cout<<"1"<<endl;}}return 0;
}


这篇关于POJ1067 取石子游戏(博弈论)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1105009

相关文章

poj1067(威佐夫博奕)

题意:给两堆石头,两种操作,1、在任意一堆中去任意个石头;2、在两堆中去相同多个石头 必败状态为(0,0)(1,2)(3,5)(4,7)(6,10 )  ( 8 ,13 ) (9,15)、(11,18)、(12,20)。。。。。 然后请参照http://blog.csdn.net/u013509299/article/details/37954679 代码如下: #include<io

国产游戏崛起:技术革新与文化自信的双重推动

近年来,国产游戏行业发展迅猛,技术水平和作品质量均得到了显著提升。特别是以《黑神话:悟空》为代表的一系列优秀作品,成功打破了过去中国游戏市场以手游和网游为主的局限,向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展,国产游戏正逐步赢得国际市场的认可。然而,面对全球游戏行业的激烈竞争,国产游戏技术依然面临诸多挑战,未来的

火柴游戏java版

代码 /*** 火柴游戏* <p>* <li>有24根火柴</li>* <li>组成 A + B = C 等式</li>* <li>总共有多少种适合方式?</li>* <br>* <h>分析:</h>* <li>除去"+"、"="四根,最多可用火柴根数20根。</li>* <li>全部用两根组合成"1",最大数值为1111。使用枚举法,A和B范围在0~1111,C为A+B。判断</li>** @

国产游戏行业的崛起与挑战:技术创新引领未来

国产游戏行业的崛起与挑战:技术创新引领未来 近年来,国产游戏行业蓬勃发展,技术水平不断提升,许多优秀作品在国际市场上崭露头角。从画面渲染到物理引擎,从AI技术到服务器架构,国产游戏已实现质的飞跃。然而,面对全球游戏市场的激烈竞争,国产游戏技术仍然面临诸多挑战。本文将探讨这些挑战,并展望未来的机遇,深入分析IT技术的创新将如何推动行业发展。 国产游戏技术现状 国产游戏在画面渲染、物理引擎、AI

第四次北漂----挣个独立游戏的素材钱

第四次北漂,在智联招聘上,有个小公司主动和我联系。面试了下,决定入职了,osg/osgearth的。月薪两万一。 大跌眼镜的是,我入职后,第一天的工作内容就是接手他的工作,三天后他就离职了。 我之所以考虑入职,是因为 1,该公司有恒歌科技的freex平台源码,可以学学,对以前不懂的解解惑。 2,挣点素材钱,看看张亮002的视频,他用了6000多,在虚幻商城买的吸血鬼游戏相关的素材,可以玩两年。我

nyoj 1038 纸牌游戏

poj 的一道改编题,说是翻译题更恰当,因为只是小幅度改动。 一道模拟题,代码掌控能力比较好,思维逻辑清晰的话就能AC。 代码如下: #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{char c[5];int rk;char da[5];int nu

如果出一个名叫白神话悟空的游戏

最近黑神话由于与原著不符引起了原著派的争议。 所以我在摸鱼的时候想到如果游科或者某个别的公司“痛改前非”不夹带私货完全复刻吴承恩百回版剧情制作一个“重走西游路”的游戏,会有一个什么样的销量?(设定为原著派已经多方渠道认证,此游戏的确没有夹带私货,绝大部分复刻了原著剧情) 游戏玩法我想了几类 超长线性有岔路蜈蚣形状地图,蜈蚣的腿部是探索区域和支线,重走西游路线,开篇就是开始取经前唐玄宗御弟cg

《黑暗之魂2:原罪学者》是什么类型的游戏 《黑暗之魂》可以在苹果Mac电脑上玩吗?

在宏大的世界观游戏中,《黑暗之魂2:原罪学者》脱颖而出,以其探索性和挑战性征服了全球玩家的心灵。下面我们来看看《黑暗之魂2:原罪学者》是什么类型的游戏,《黑暗之魂2:原罪学者》可以在苹果电脑玩吗的相关内容。 一、《黑暗之魂2:原罪学者》是什么类型的游戏 《黑暗之魂2:原罪学者》作为《黑暗之魂2》的增强版和重制版,是一款FromSoftware制作、BANDAI NAMCO和FromSoft

简单取石子游戏~博弈

很坑爹的小游戏,至于怎么坑爹,嘎嘎~自己研究去吧~! #include<stdio.h>#include<windows.h>#include<iostream>#include<string.h>#include<time.h>using namespace std;void Loc(int x,int y);/*定位光标*/void Welcome(); /*创建欢迎界面*/

黑神话:悟空》增加草地绘制距离MOD使游戏场景看起来更加广阔与自然,增强了游戏的沉浸式体验

《黑神话:悟空》增加草地绘制距离MOD为玩家提供了一种全新的视觉体验,通过扩展游戏中草地的绘制距离,增加了场景的深度和真实感。该MOD通过增加草地的绘制距离,使游戏场景看起来更加广阔与自然,增强了游戏的沉浸式体验。 增加草地绘制距离MOD安装 1、在%userprofile%AppDataLocalb1SavedConfigWindows目录下找到Engine.ini文件。 2、使用记事本编辑