前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ACM刷题之路(十)博弈论 jack & rose

ACM刷题之路(十)博弈论 jack & rose

作者头像
Designer 小郑
发布2023-07-31 15:39:20
1480
发布2023-07-31 15:39:20
举报
文章被收录于专栏:跟着小郑学JAVA跟着小郑学JAVA

J jack & rose


时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte 总提交:139            测试通过:52

描述

Jack 和 Rose在泰坦尼克号上邂逅后(1912年),一起玩起了博弈,当时还没博弈论(博弈论,1913年才开始有人研究),但是2人都很聪明,都能够选择最优策略。Jack 和 Rose相对而坐,面前有n个石块,两个人轮流从中取石块,规定每次至少取一个,最多取m个,最后取光者得胜。因为2人关系不一般,游戏规则有点改变,每次开局,Rose先取,而Jack每次最多可以取m+1个,Rose还是最多取m个。

输入

 输入有多组数据,每组输入int范围内的整数n , m。

输出

 每一局的胜利者姓名。

样例输入

1 1 2 1

样例输出

Rose Jack

元培OJ2011   15年院赛J题


题解:

理论上来说:

R如果想赢,就必须给J留M+2个石头;

J如果想赢,就必须给R留M+1个石头;

比如每人最多拿10个石头,目前余下来11个石头的时候,先拿的必输。

但是J可以比R多拿一个,面对R给J留的M+2的难题时,可以取一个,反而转化为J给R留M+1个石头,最后让J胜利。

除非R一下子全部拿完,不然就是J赢。

换句话说,J可以抵挡住R的杀手锏,而R不能抵挡住J的杀手锏,导致J是赢家。


AC代码:

代码语言:javascript
复制
#include<iostream>
using namespace std;

int main()
{
	int n, m;
	while (cin >> n >> m) {
		if (n > m)
			cout << "Jack" << endl;
		else
			cout << "Rose" << endl;
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-09-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • J jack & rose
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档