NY562 & CSU1104 盒子遊戲【博弈】

盒子遊戲

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 3

描述

    有兩個相同的盒子，其中一個裝了 n 個球，另一個裝了一個球。Alice 和 Bob 發明了一個遊戲，規則如下：Alice 和 Bob 輪流操作，Alice 先操作。每次操作時，遊戲者先看看哪個盒子裡的球的數目比較少，然後清空這個盒子（盒子裡的球直接扔掉），然後把另一個盒子裡的球拿一些到這個盒子中，使得兩個盒子都至少有一個球。如果一個遊戲者無法進行操作，他（她）就輸了。下圖是一個典型的遊戲：       

    面對兩個各裝一個球的盒子，Bob 無法繼續操作，是以 Alice 獲勝。你的任務是找出誰會獲勝。假定兩人都很聰明，總是采取最優政策。

輸入

輸入最多包含 300 組測試資料。每組資料僅一行，包含一個整數 n（2<=n<=10^9）。輸入結束标志為 n=0。

輸出

對于每組資料，輸出勝者的名字。

樣例輸入

2 
3 
4 
0       

樣例輸出

Alice 
Bob 
Alice       

來源

湖南省第七屆大學生計算機程式設計競賽

原題連結：http://acm.nyist.net/JudgeOnline/problem.php?pid=562

基礎博弈。

簡單推導後n為3,7,15,31....(a[n] = a[i-1] *2+1) 時先手必敗。

開始想到打表，把那些數字标記，後來意料之中的MLE，畢竟n<=10^9;後來找出範圍内的必敗點，就OK了

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100000];
int main()
{
    a[0]=1;
    for (int i=1;i<30;i++)
    {
        a[i]=a[i-1]*2+1;
    }
    int n;
    //freopen("4.txt","r",stdin);
    while(cin>>n,n)
    {
        bool flag=true;
        for(int i=0;i<30;i++)
            if(a[i]==n)
                flag=false;
        if(flag)
            cout<<"Alice"<<endl;
        else
            cout<<"Bob"<<endl;
    }
    return 0;
}