Box Game
Input: Standard Input
Output: Standard Output
There are two identical boxes. One of them contains n balls, while the other box contains one ball.
Alice and Bob invented a game with the boxes and balls, which is played as follows:
Alice and Bob moves alternatively, Alice moves first. For each move, the player finds out the box
having fewer number of balls inside, and empties that box (the balls inside will be removed forever),
and redistribute the balls in the other box. After the redistribution, each box should contain at least one
ball. If a player cannot perform a valid move, he loses. A typical game is shown below:
When both boxes contain only one ball, Bob cannot do anything more, so Alice wins.
Question: if Alice and Bob are both clever enough, who will win? Suppose both of them are very
smart and always follows a perfect strategy.
Input
There will be at most 300 test cases. Each test case contains an integer n (2<=n<=109) in a single line.
The input terminates by n=0.
Output
For each test case, print a single line, the name of the winner.
Sample Input
2
3
4
0
Output for Sample Input
Alice
Bob
Alice
Problemsetter: Rujia Liu, Special Thanks: Yiming Li & Jane Alam Jan
题意:
给出 n,代表有一个筐子有 n 个球,另一个筐子有 1 个球。游戏由 Alice 开始,每次先把两个筐子中小的球取出来,再将另一个筐子中的球分任意个到另一个筐子中。如果当遇到不能取出球的情况,则另一个人为赢。输出最后赢的人。
思路:
规律。当遇到偶数的时候,则那个人就会赢,所以每次分出去的一定要是个偶数。所以如果是偶数的话,绝对会是 Alice 赢。所以考虑奇数的情况。
3 -> B 相反赢
5 -> A 本身赢
7 -> B 相反赢
9 -> A 本身赢
11 -> A 本身赢
13 -> A 本身赢
15 -> B (可以分的情况为 2 - 13,4 - 11, 6 - 9,因为这几种情况都是本身赢,分出去之后先权就轮到了 Bob,所以就是 Bob 赢)……
类似情况继续讨论,就会得到,Bob 会在 ai = ai-1 X 2 + 1 赢。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int n; while (~scanf("%d", &n) && n) { if (n % 2) { while (n > 10) { --n; if (n % 2) break; n /= 2; } if (n ==3 || n == 7) puts("Bob"); else puts("Alice"); } else puts("Alice"); } return 0; }
相关推荐
推箱子游戏java代码,eclipse可以直接导入,也可以用intellij idea等ide打开
利用python的pygame框架开发的推箱子小游戏,业余时间可以拿来娱乐一下,回忆经典
基于easyx的c小程序推箱子,功能实现完全,可以简单自行加地图
BoxGame
java课设,内含1、《泡泡堂》游戏,2、登陆注册界面,3、仿QQ的用户交流,server/client联机,传输信息,4、用到MySQL数据库
Introduction to Game Physics with Box2D 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,...
C语言推箱子游戏(二维数组)C_boxGame-master.zip
GameBox_SDK_RELEASE_V1.5.4.0_70.zip
BoxGame_Launcher 用 Java 编写 BoxGame 的游戏启动器
gamebox*****
GameBox_01.app.iml
CSS3中的box-sizing(content-box与border-box) CSS3中的box-sizing 属性允许以特定的方式来指定盒模型,有两种方式: content-box:标准盒模型,又叫做 W3C盒模型,一般在现代浏览器中使用的都是这个盒模型 border...
该项目是Nadeo游戏(例如TrackMania Nations Forever)中使用的GameBox游戏引擎的开源重新实现 如何建造 先决条件 使用以下命令克隆存储库: git clone https://github.com/ProtoByter/ReMania-GameBox --recurse-...
JavaScript
3D-glory-box-game.zip,浏览器三维平台游戏,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用程序。
基于Qt开发的GameBox主机游戏模拟器可在windows/macos/linux多平台使用,适合毕业设计、课程设计、项目开发。项目源码已经过严格测试,可以放心下载使用~ 基于Qt开发的GameBox主机游戏模拟器可在windows/macos/...
JavaScript
Box2d简介 Box2d简介 Box2d简介 Box2d简介
matlab code for box counting dimension