UVA12585_Poker End Games

题目是这样的，每个人手中有a和b的钱数，c为a和b中间最小的一个。

每个回合，两个人胜利的概率都是0.5，胜利者从失败者手中获得c的钱数。

如果有一个人手中没钱的话，那么他就failer，游戏结束。

现在给你初始状态问你这次游戏需要进行的回合以及A胜利的期望值分别为多少？

这样的，自己手动模拟几组数据就会发现胜利的概率就是a/(a+b)。

对于回合数，我们可以深搜，但是有的可能有环，所以我们只要设置深搜上线只需要深度为20即可。因为超过20的肯定不会对小数前五位产生影响。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int a,b,n,m,k=;

double ans1,ans2;

double dfs(int x,int y,int tep)

{

    if (tep>) return ;

    if (x== || y==) return ;

    int cur=min(x,y);

    return +0.5*(dfs(x-cur,y+cur,tep+)+dfs(x+cur,y-cur,tep+));

}

int main()

{

    scanf("%d",&n);

    m=;

    while (n--)

    {

        scanf("%d%d",&a,&b);

        ans2=(double)a/(a+b);

        ans1=dfs(a,b,);

        printf("Case %d: %.6lf %.6lf\n",++m,ans1,ans2);

    }

    return ;

}

巴特西

UVA12585_Poker End Games

最新文章

热门文章