洛谷——P4018 RoyOctober之取石子

P4018 Roy&October之取石子

题目背景

Roy和October两人在玩一个取石子的游戏。

题目描述

游戏规则是这样的：共有n个石子，两人每次都只能取p^kpk个（p为质数，k为自然数，且p^kpk小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在October先取，问她有没有必胜策略。

若她有必胜策略，输出一行"October wins!"；否则输出一行"Roy wins!"。

输入输出格式

输入格式：

第一行一个正整数T，表示测试点组数。

第2行~第(T+1)行，一行一个正整数n，表示石子个数。

输出格式：

T行，每行分别为"October wins!"或"Roy wins!"。

输入输出样例

3
4
9
14

October wins!
October wins!
October wins!

说明

对于30%的数据，1<=n<=30；

对于60%的数据，1<=n<=1,000,000；

对于100%的数据，1<=n<=50,000,000，1<=T<=100,000。

（改编题）

乍一看像是博弈

其实数学归纳法也可以完成这个题目

我们来看下面的表格

当棋子的个数小于等于6的时候，我们可以看到在1~5的时候全是第一个人赢，当n=6是第二个人赢，当7~11内我们可以将数拆成1~5内的一个数想让第一个人拿，然后余出个6，这样第二个人就不可能一次拿完，只能再让第一个人拿一次，这样第一个人必胜，当12时，第二个人赢、、、以此类推，我们可以发现，当n为6的倍数的时候，第二个人赢，其余情况均为第一个人赢

#include
#include
#include
#include
using namespace std;
int T,n;
int read()
{int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int main()
{T=read();while(T--){n=read();if(n%6==0) printf("Roy wins!\n");else printf("October wins!\n");}return 0;
}

转载于:https://www.cnblogs.com/z360/p/8156806.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！