基础博弈问题

港控/mmm° 2022-05-22 09:10 161阅读 0赞

### Guns and Roses （1） ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

#### Problem Description ####

Guns和Roses是两个好朋友，这一天他们比赛吃葡萄。假定他们有ANS颗葡萄。

在比赛之前他们会首先确定每次吃葡萄的数量的最大值为S，和ANS的具体值。

两个人轮流吃葡萄，每次最多吃S颗，不能不吃。（即假定每次吃M颗葡萄，则 1<=M<=S）

游戏规定在谁吃完葡萄后,他们两个人所吃的葡萄总和等于ANS，谁就获胜。

假定他们两人足够聪明，在吃葡萄的过程中都不会使值大于ANS。

现在规定Guns先手，请你帮助他计算为了确保最终取得胜利，他第一次应该吃多少颗葡萄？

若第一次无论吃多少颗葡萄，最终都无法取得胜利，请你输出 -1 。

#### Input ####

输入数据有多组，到 EOF 结束。

对于每组数据，输入有一行，包含用空格隔开的两个整数ANS，S。

*  1<=S<=2000
 *  1<=ANS<=1000000

#### Output ####

对于每组数据，输出一行。

这一行包含一个整数，即Guns为了保证最终取得胜利第一次选择所吃的葡萄数目。（若无法保证最终取得胜利，则输出 -1）

#### Sample Input ####

9 4
    123 8
    14 6

#### Sample Output ####

4
    6
    -1

思路：

![70][]

当ans除于（1+s）的余数为零的时候，就是Guns无论怎样取先手都不可能获胜的情况，既要输出-1；因为无论你现先手取任何数s1，roses只需要取（1+s）-s1他就会获胜。

代码如下：

![70 1][]

[Submit]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2543/pid/4239.html
[Statistic]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2543/pid/4239.html
[70]: /images/20220522/470f3c757db749e4896ea7cd9ae9bfff.png
[70 1]: /images/20220522/0a7042174a2a4e96bbe60c8a369bbbe8.png

发表评论取消回复

表情：

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

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

相关阅读

相关三个博弈基础

（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。显然，如果n=m+1，那么由于一次最多

待我称王封你为后i/ 2023年07月02日 04:23/ 0 赞/ 30 阅读

相关棋类博弈

[五子棋AI设计][AI] [博弈树搜索][Link 1] [象棋百科全书][Link 2] [人工智能搜

冷不防/ 2022年09月24日 01:29/ 0 赞/ 343 阅读

相关一个有意思的博弈问题

翻书看到一道挺有意思的博弈问题，据说是冯.诺伊曼提出来的。 "三个人持枪决斗。A的枪法最差，成功率为1/3；B的成功率稍好，为2/3;C的枪法最准，每击必中。决斗规则

男娘i/ 2022年09月20日 06:05/ 0 赞/ 258 阅读

相关博弈树

中秋在家,和闺女下棋,连续输棋,遂决定作弊,写个程序求下最优解. 棋是立体的一字棋,七列,六行,交替落子,每个棋子可以选择任一列放置,自动落到本列最低的空位上.

迈不过友情╰/ 2022年09月19日 10:52/ 0 赞/ 207 阅读

相关博弈之威佐夫博弈详解

威佐夫博弈是博弈中的另一个经典模型。问题：首先有两堆石子，博弈双方每次可以取一堆石子中的任意个，不能不取，或者取两堆石子中的相同个。先取完者赢。分析：首

柔光的暖阳◎/ 2022年08月26日 01:15/ 0 赞/ 221 阅读

相关基础博弈问题

Guns and Roses （1） Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic

港控/mmm°/ 2022年05月22日 09:10/ 0 赞/ 162 阅读

相关博弈问题

博弈问题巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取

曾经终败给现在/ 2022年05月18日 02:23/ 0 赞/ 248 阅读

相关博弈问题

[http://weilog.lanqiao.org/2018/03/17/altraining\_ep5/][http_weilog.lanqiao.org_2018_03_

╰+攻爆jí腚メ/ 2022年04月12日 14:15/ 0 赞/ 233 阅读

相关动态规划之博弈问题

点击蓝色“五分钟学算法”关注我哟加个“星标”，一起学算法 ![640][] 作者 | labuladong 来源 | labuladong 博弈类问题的套

电玩女神/ 2021年11月09日 05:10/ 0 赞/ 441 阅读

相关棋盘博弈

给定无限大棋盘, 每个格子能染为黑白两种颜色, 初始全白. 初始位置(1,1)有一个棋子, Alice和Bob轮流操作, Alice先手, 每次操作假设棋子在(x,y),

ゝ一纸荒年。/ 2021年11月05日 22:34/ 0 赞/ 371 阅读