Problem 3 放球游戲(ball.cpp/c/pas)
【題目描述】
Stas和Masha發明了一個游戲。游戲道具是a個兩兩不同的箱子和b個兩兩不同的皮球，Stas和Masha輪流操作，且每次操作新增一個完全不同的箱子或皮球。如果Stas或Masha操作了以後，把b個皮球放進a個箱子的方案數不小於n，那麼這個人就會輸掉。所有箱子和皮球都是不同的，可以有空的箱子。
如果第一回合由Stas先操作，且Stas和Masha都按照最優策略進行游戲，那麼是否會打平？如果不打平，誰會輸？？
【輸入格式】
輸入的第一行包含三個正整數a，b，n。
【輸出格式】
如果Stas會輸，輸出'Stas'（不要輸出引號）；如果Masha會輸，輸出'Masha'； 如果游戲會打平（也就是不結束），輸出'Missing'。
【樣例輸入】
樣例一:2 2 10
樣例二:5 5 16808
樣例三:3 1 4
樣例四:1 4 10
【樣例輸出】
樣例一:Masha
樣例二:Masha
樣例三:Stas
樣例四:Missing
【數據范圍】
對於10%的數據，n不超過10；
對於30%的數據，n不超過10000。
對於100%的數據，1≤a≤10,000, 1≤b≤30, 2≤n≤1,000,000,000, a^b
博弈a^b=n
把a>1的所用情況記憶化（情況數少）
唯一平局的情況是
a=1 b=x
(a+1)^b爆
還有一種是
1^x 2^x爆 判奇偶
其實不記憶化也能過（汗-_-)。
[cpp]
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (1000000000)
#define MAXA (10000+10)
#define MAXB (30+10)
long long a,b,n;
bool pow2(long long a,long long b)
{
long long ans=1;
for(int i=1;i<=b;i++)
{
ans*=a;
if (ans>=n) return 0;
}
return 1;
}
int dfs(long long a,long long b) //a,b狀態保證合法 0 Miss 1 Win -1 Lost
{
if (a==1&&!pow2(a+1,b)) return 0;
int flag=-1;
if (a==1)
{
if (pow2(a+1,b)) flag=max(-dfs(a+1,b),flag);
if (flag==1) return 1;
if (pow2(a,b+1)) flag=max(-dfs(a,b+1),flag);
return flag;
}
else
{
if (pow2(a,b+1)) flag=max(-dfs(a,b+1),flag);
if (flag==1) return 1;
if (pow2(a+1,b)) flag=max(-dfs(a+1,b),flag);
return flag;
}
}
int main()
{
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
scanf("%d%d%d",&a,&b,&n);
/*
if (a==1&&!pow2(a+1,b))
{
return 0;
}
else if (b==1&&!dfs(a,b+1))
{
}
*/
int p=dfs(a,b);
if (p==0) printf("Missing\n");
else if (p==-1) printf("Stas\n");
else printf("Masha\n");
return 0;
}
