游戏(atlantis)"/>
1984. 【普及组模拟赛】游戏(atlantis)
1984. 【普及组模拟赛】游戏(atlantis)
题目描述
Atlantis Island 沉没以前,传说中的猫老大和 King 是好朋友……King 很喜欢赌博,这次 King和老朋友猫老大多年不见, 于是便邀请猫老大来玩一个游戏,猫老大应邀参加了。 King 拿出了 n 块黄金(0<n<10^1000002), 猫老大暗自想:咋来这么多钱的……现在 King 和猫老大轮流从黄金中拿走一些,每人每次拿走的块数是 2 的次方(例如 1,2,4,8,16……)谁能拿走最后一个黄金,谁就获胜。 现在 King 让猫老大先拿,双方都使用最好的策略来玩的话,谁能取得胜利呢?现在请你来帮助猫老大,他能胜利吗?不仅如此, King 现在提出要和猫老大玩三局,猫老大想知道每局他是否能获胜,并且,你还要告诉猫老大,如果必胜的话,他第一步最少拿走的金块数量。
输入
三行每行一个数 n(0<n<10^1000002)。
输出
对于每局, 如果 King 必胜则输出一行“ King will win.”; 否则第一行输出“ MaoLaoDa will win.”, 第二行输出他第一次拿的最小数量。
样例输入
样例输入1:
8
4
2
样例输入2:
3
8
2
样例输出
样例输出1
MaoLaoDa will win.
2
MaoLaoDa will win.
1
MaoLaoDa will win.
2
样例输出2
King will win.
MaoLaoDa will win.
2
MaoLaoDa will win.
2
数据范围限制
0<n<10^1000002
思路:
一看题目我们便知道这是一道博弈论。那怎去做呢?
从小数据推起。
金块数量 | 获胜者 | 猫老大的第一次最优方案 |
---|---|---|
1 | 猫老大 | 取1 |
2 | 猫老大 | 取2 |
3 | King | 取1 |
4 | 猫老大 | 取1 |
5 | 猫老大 | 取2 |
6 | King | 取1 |
7 | 猫老大 | 取1 |
8 | 猫老大 | 取2 |
9 | King | 取1 |
… | … | … |
通过上表我们可以发现只要金块数为3的倍数,则猫老大必输:反之猫老大必赢。
然后我们看看数据范围,101000002,是不是第一时间会想用高精度。其实不是的,想想小学知识,如何判断一个数是3的倍数?不就是各位相加为3的倍数就行了吗。那按这样,最大值也才:9*1000002。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e6;
string a;
int main()
{fre(atlantis);for(int i=1;i<=3;i++){cin>>a;int l=a.size(),tot=0;for(int j=0;j<l;j++) tot+=(a[j]-'0');if(!(tot%3)) printf("King will win.\n");else printf("MaoLaoDa will win.\n%d\n",tot%3);}return 0;
}
更多推荐
1984. 【普及组模拟赛】游戏(atlantis)
发布评论