vijos1196|吃糖果游戏|博弈论

摘要:
描述一下矩阵67和暗影正在玩一个小游戏。桌子上有两堆糖果。矩阵67和阴影轮流操作这些糖果。游戏规定,操作员要吃最后一块糖果才能获胜。Matrix67和Shadow将玩10场游戏,Matrix67将始终在每场游戏中首先运行。Matrix67想知道谁在每场比赛中都有获胜策略。这些字符串只能是“Matrix67”或“Shadow”。他们在相应的十行输入数据中代表具有获胜策略的一方。示例1样本输入111121314152122232425样本输出1矩阵67矩阵67矩阵47矩阵67阴影矩阵67矩阵77限制每个测试点的1s来源矩阵67的原始分析:这个问题并不难。

描述
Matrix67和Shadow正在做一个小游戏。
桌子上放着两堆糖果,Matrix67和Shadow轮流对这些糖果进行操作。在每一次操作中,操作者需要吃掉其中一堆糖果,并且把另一堆糖果分成两堆(可以不相等)留给对方操作。游戏如此进行下去,糖果数会越来越少,最后必将出现这样一种情况:某人吃掉一堆糖果后发现另一堆里只剩一块糖果不能再分了。游戏规定此时该操作者吃掉最后这一块糖果从而取胜。
这个游戏是不公平的。对于任意一种初始状态,总有一方有必胜策略。所谓有必胜策略是指,无论对方如何操作,自己总有办法取胜。
Matrix67和Shadow将进行10次游戏,每一次游戏中总是Matrix67先进行操作。Matrix67想知道每一次游戏中谁有必胜策略。
格式
输入格式
输入数据一共10行,每行有两个用空格隔开的正整数,表示一次游戏开始时桌子上两堆糖果分别有多少个。
对于50%的数据,这些正整数均不超过100;
对于70%的数据,这些正整数均不超过10 000;
对于100%的数据,这些正整数均不超过10 000位。
输出格式
输出十行字符串。这些字符串只能是“Matrix67”或“Shadow”,它们表示对应的十行输入数据中有必胜策略的一方。
请注意大小写。
样例1
样例输入1
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
样例输出1
Matrix67
Matrix67
Matrix67
Matrix67
Matrix67
Matrix67
Shadow
Shadow
Matrix67
Matrix67
限制
各个测试点1s
来源
Matrix67原创

分析:这题其实不难。与萌萌的糖果那道题类似。我还是从头分析一下,给像我一样的蒟蒻引路。

我们假设两堆a,b,先吃a。

如果是a,1,显然67胜。如果是a,2,显然67挂了。如果是a,3,3=1+2,67还是挂。如果是a,4,4=2+2。67胜了。

如果是a,5或6,5=2+3,6=3+3,67胜。如果a,7,若7=2+5,s可以吃掉2然后分成2+3,67挂;若7=1+6,s可以拿走1然后分成3+3;

若7=2+5,s可以吃掉2然后分成2+3。所以a,7的话67必挂。如果是a,8,同7的情况67挂了。如果是a,9,恭喜9=2+7,s必挂无疑。

如果是a,10。10=2+8,于是你又赢了。

我们可以定义集合a={2,3,7,8},b={1,4,5,6,9,10}。

考虑两堆都大于10的情况。

(1)10*i+a,10*i+a。则67必输。

(2)10*i+a,10*i+b,你可以吃掉10*i+a,然后把10*i+b分成两堆10*i+a,67必胜。

(2)10*i+b,10*i+b,67必胜。

免责声明:文章转载自《vijos1196|吃糖果游戏|博弈论》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【字符串入门专题1】C自定义ToggleButton的样式下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

git 系列4(文件提交历史)

1查看文件提交历史记录。如果gitlog命令默认不使用任何参数,gitlog将提交时间中列出的所有更新,最新的更新位于顶部;每次更新都有一个SHA-1校验和、作者的姓名和电子邮件地址以及提交时间。提交说明通过在末尾缩进一段来显示——Stat显示每次更新的文件修改统计信息。您还可以给出几个搜索条件并列出符合条件的提交——提交者只显示与指定提交者相关的提交。...

基于 WebRTC 的 RTSP 视频实时预览

该方案采用基于WebRTC的视频即时消息,其原生支持RTP协议的解码,因此延迟可以非常低,约为0.2-0.4秒。其他方案的延迟大于1秒。WebRTC需要浏览器。您可以在以下地址查看支持的浏览器。WebRTC实现基于web的视频会议。标准是WHATWG协议。其目的是通过浏览器提供简单的javascript来实现实时通信功能。Github中有很多WebRTC的实...

差分方程的零输入响应与零状态响应

差分方程的迭代分析方法有以下缺点:没有闭合解,不利于数学分析。某个时间的输出只能从头开始计算。本文介绍了差分方程的零输入响应和零状态响应分析方法。对于系统,这种分析方法可以很好地表达系统响应的物理意义=Y[-1]=0$Input Y[n]。回顾零输入响应和零状态响应的迭代计算,我们发现以下规则:$egin{align*}y[0]&=-&qqu...

微信小程序-获取input值的两种方法

1、bindinput其中e.detail是获取input数据其中包含value值,cursor是获取光标的位置。...

sql server 日志软件过大设置办法

在使用sqlserver的过程中,sql日志文件的大小将随着其增长而受到限制。1.找到相应的库--˃属性--˃恢复模式,并将其更改为简单模式。2.选择库--˃任务--˃收缩--˃文件。3.选择日志文件收缩或数据库文件收缩。删除命令后占用的空间将在此处释放。数据库ldf文件的占用空间将更改为设置的空间大小。...