Two Nikifors play a funny game. There is a heap ofNstones 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 numberN(conditionN≤ 10250holds).
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
这也是个有趣的问题,也很经典的游戏题目的变形了。
不过这道题扩展了成为无限大的数了。
类似的游戏有:没人可以拿掉桌面上的棋子,每次不能超过5个,最后没棋子可以拿的算输
解决这样的题目只能是寻找规律了,不能真的模拟区玩了,否则必定超时。
这道题目的规律就是:
1 如果给出的stone是3的倍数,那么先取者必输
2 如果给出的不是3的倍数,那么先取者就凑成3的倍数就必赢,因为凑3的倍数很容易,去掉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;
}
分享到:
相关推荐
Times New Roman.TTF,字体文件
detecing network modules in fMRI times series .pdf
6 Trends on 'Perception' for ADAS_AV _ EE Times.pdf麻省理工AI神经网络ADAS6 Trends on 'Perception' for ADAS_AV _ EE Times.pdf麻省理工AI神经网络ADAS6 Trends on 'Perception' for ADAS_AV _ EE Times.pdf...
The.Essential.Guide.to.SAS.Dates.and.Times.Jun.2006
苦苦寻找的times文件,用于KITTI数据集SLAM测试 苦苦寻找的times文件,用于KITTI数据集SLAM测试 苦苦寻找的times文件,用于KITTI数据集SLAM测试
Android Times Square介绍: 效果不错的日历UI模块。可以设置成只能选择单个日期,或者可以选择多个不连续的日期,或者可以通过点击两个日期来选择之间连续的日期。并且可以将日历放到弹出的对话框中。 测试...
Good Economics For Hard Times.pdf
Project budgets are smaller, production times are shorter, and milestones seem to come more often, especially when working with a publisher. With the increased time and expertise required to engineer...
开源项目-djherbis-times.zip,File Times for Go (atime, mtime, ctime, btime)
SAP ABAP 开发 SMARTFORMS字体,SE73 Times New Roman.ttf
27Modern_Times_ExtraPack.rar 27Modern_Times_ExtraPack.rar
( Times New Roman.rar
Times New Roman .fon
资源来自pypi官网。 资源全名:mo-times-2.27.18331.tar.gz
资源分类:Python库 所属语言:Python 资源全名:mo-times-5.53.21241.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
2. Building the Core Game Framework 9 2.1 Controllers and Managers............................................11 2.1.1 Controllers................................................11 2.1.2 Managers........