首页 > 代码库 > Timus 1180. Stone Game 游戏题目
Timus 1180. Stone Game 游戏题目
Two Nikifors play a funny game. There is a heap of N stones in front of them. Both Nikifors in turns take some stones from the heap. One may take any number of stones with the only condition
that this number is a nonnegative integer power of 2 (e.g. 1, 2, 4, 8 etc.). Nikifor who takes the last stone wins. You are to write a program that determines winner assuming each Nikifor does its best.
Input
An input contains the only positive integer number N (condition N ≤ 10250 holds).
Output
The first line should contain 1 in the case the first Nikifor wins and 2 in case the second one does. If the first Nikifor wins the second line should contain the minimal number of stones he should
take at the first move in order to guarantee his victory.
Sample
| input | output |
|---|---|
8 |
1 2 |
这也是个有趣的问题。也非常经典的游戏题目的变形了。
只是这道题扩展了成为无限大的数了。
类似的游戏有：没人能够拿掉桌面上的棋子，每次不能超过5个，最后没棋子能够拿的算输
解决这种题目仅仅能是寻找规律了，不能真的模拟区玩了。否则必然超时。
这道题目的规律就是：
1 假设给出的stone是3的倍数。那么先取者必输
2 假设给出的不是3的倍数。那么先取者就凑成3的倍数就必赢。由于凑3的倍数非常easy，去掉1个或者2个必然能够凑出来了
所以最后问题就成了mod3问题了。
我是怎么想出来的？
我是一个列子一个样例去观察，最后得出结论的，然后验证。AC。结论正确。
也挺花时间的。
#include <string>
#include <iostream>
using namespace std;
int StoneGameMod3(string &s)
{
int carry = 0;
for (int i = 0; i < s.size(); i++)
{
int a = carry * 10 + s[i] - ‘0‘;
carry = a % 3;
}
return carry;
}
void StoneGame1180()
{
string s;
cin>>s;
int mod3 = StoneGameMod3(s);
if (0 == mod3) cout<<2;
else cout<<1<<endl<<mod3;
}
int main()
{
StoneGame1180();
return 0;
}
Timus 1180. Stone Game 游戏题目
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。