放球游戏(a^b博弈)

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<n

博弈a^b=n

把a>1的所用情况记忆化(情况数少)

唯一平局的情况是

a=1 b=x 

(a+1)^b爆 

还有一种是

1^x 2^x爆 判奇偶

其实不记忆化也能过(汗-_-)。

#include<cstdio>

include<cstring>

include<algorithm>

include<functional>

include<cstdlib>

include<cmath>

include<iostream>

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&amp;&amp;!dfs(a,b+1))
{

}
*/
int p=dfs(a,b);
if (p==0) printf(&quot;Missing\n&quot;);
else if (p==-1) printf(&quot;Stas\n&quot;);
else printf(&quot;Masha\n&quot;);   
return 0;

}