首页 > 代码库 > 盒子游戏

盒子游戏

水水的~=~
1254: 盒子游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
[Submit][Status][Web Board]

Problem Description

有两个相同的盒子,其中一个装了n个球,另一个装了一个球。Alice和Bob发明了一个游戏,规则如下:Alice和Bob轮流操作,Alice先操作。每次操作时,游戏者先看看哪个盒子里的球的数目比较少,然后清空这个盒子(盒子里的球直接扔掉),然后把另一个盒子里的球拿一些到这个盒子中,使得两个盒子都至少有一个球。如果一个游戏者无法进行操作,他(她)就输了。下图是一个典型的游戏:

面对两个各装一个球的盒子,Bob无法继续操作,因此Alice获胜。你的任务是找出谁会获胜。假定两人都很聪明,总是采取最优策略。

Input

输入最多包含300组测试数据。每组数据仅一行,包含一个整数n(2<=n<=10^9)。输入结束标志为n=0。

Output

对于每组数据,输出胜者的名字。

Sample Input

2
3
4
0

Sample Output

Alice
Bob
Alice

HINT

Source

湖南省第七届大学生程序设计大赛

Difficulty

Author

admin


这题还有点意思  博弈~

如果 n=2^i  - 1 (i=2,3,4,5.........) 第一个人必败!

因为 你为int 型 所以 必败型 可以预处理出来~

然后 枚举即可

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#define PI acos(-1.0)
#define eps 1e-8
#define LL long long
#define moo 31536000
#define INF 1e9
#define maxn 100010
using namespace std;
int dp[35];
int main()
{
    dp[0]=1;
    for(int i=1;i<=30;i++)
    dp[i]=dp[i-1]*2+1;
    int n;
    while(~scanf("%d",&n) && n)
    {
        int flag=0;
      for(int i=1;i<29;i++)
        if(n==dp[i])
        {
            flag=1;
            break;
        }
        if(flag)
            cout<<"Bob"<<endl;
        else
            cout<<"Alice"<<endl;
 
    }
    return 0;
}
/**************************************************************
    Problem: 1254
    User: mangogo
    Language: C++
    Result: Accepted
    Time:1 ms
    Memory:1436 kb
****************************************************************/


盒子游戏