解题报告——Block Game(思维题)(Benelux Algorithm Programming Contest 2016 Preliminary)(计蒜客)

Description

You are attending the International Construction by Preschoolers Contest. Unfortunately,you are too old to participate, but you still enjoy watching the competition.In between rounds, you are walking around the contest area when you see a toddler, one ofthe contestants, playing with her blocks. Annoyed that she is having all the fun, you decideto challenge her to a game.You set up two stacks of blocks of a certain height. Then, you and the toddler take turnsremoving some number of blocks from the stack which contains the largest number of blocks(if both stacks have the same number of blocks, the current player can choose either stackto remove blocks from). The number of blocks removed must be a positive multiple of thenumber of blocks in the smaller stack. For instance, if there is a stack with 5 blocks, and onewith 23 blocks, then the current player can remove 5, 10, 15 or 20 blocks from the stack of23 blocks. The player who empties one of the stacks wins the game.You have graciously decided to take the first move, but then a worry strikes you – might thisdevious preschooler still be able to beat you?

Input

One line with two integers N and M, satisfying 1 <= N,M <= 10^18, the initial sizes of the twostacks of blocks.

Output

Output a single line containing a single word: the word “win” if you are guaranteed to win if you play correctly, and the word “lose” if your opponent can force you to lose.

心路历程

卡了四个小时,成功AC,喜悦的心情无以言表

题意:甲乙玩游戏, 输入两个数, 二人轮着操作,规则是每次操作只能将较大值减去成倍的较小值,直到一个数为0,从甲开始,二者都使用最佳策略,预测甲的输赢。

本题可以模拟出三种情况:
1、若 a%b=0 则直接win
2、若(b<a<=2*b),则a和b的下一轮值只能为(b,a-b)
3、若(a>=2*b),如果a%b=1,则甲将a和b改为(a%b+b, b)。
如果a%b!=1,则甲将a和b改为(a%b, b),这样,无论如何甲一定赢。

综上所述,只需判断case2即可。

注意:用long long解题。

代码

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

void Process(ll a, ll b, ll sum) {
if((a % b == 0) || (a/b >= 2)) { cout << "win" <<endl; return; }//若为case1 & case3,直接win
else //判定case2
while(b!=1) {
ll t=b; b=a-b; a=t;
sum++;
//case2中会出现case3的情况, 如13和10
if(a/b >= 2) { cout << (sum%2==1?"lose":"win")<<endl; return; }
//b=1时,意味可以整除,则输出。输出时判定sum
if(b == 1) {
cout<<(sum%2==1?"lose":"win")<<endl;
return;
}
}
}

int main() {
ios::sync_with_stdio(false);
ll a, b;
cin>>a>>b;
if(b>a) swap(a,b);
Process(a, b, 0);
return 0;
}

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

解题报告——Block Game(思维题)(Benelux Algorithm Programming Contest 2016 Preliminary)(计蒜客)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 解题报告——Block Game(思维题)(Benelux Algorithm Programming Contest 2016 Preliminary)(计蒜客)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏