当前位置:编程学习 > C/C++ >>

放球游戏(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
 
博弈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;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,