2013-12-26

HDU 糖果大战——概率论、坑题

Problem Description

生日Party结束的那天晚上，剩下了一些糖果，Gandon想把所有的都统统拿走，Speakless于是说：“可以是可以，不过我们来玩24点，你不是已经拿到了一些糖果了吗？这样，如果谁赢一局，就拿走对方一颗糖，直到拿完对方所有的糖为止。”如果谁能算出来而对方算不出来，谁就赢，但是如果双方都能算出或者都不能，就算平局，不会有任何糖果的得失。

Speakless是个喜欢提前想问题的人，既然他发起了这场糖果大战，就自然很想赢啦（不然可就要精光了-_-）。现在他需要你的帮忙，给你他每局赢的概率和Gardon每局赢的概率，请你给出他可能获得这场大战胜利的概率。

Input

每行有四个数，Speakless手上的糖果数N、Gardon手上的糖果数M(0<=N,M<=50)、一局Speakless能解答出来的概率p、一个问题Gardon能解答出来的概率q(0<=p,q<=1)。

Output

每行一个数，表示Speakless能赢的概率（用百分比计算，保留到小数点后2位）。

Sample Input

50 50 0.5 0.5

10 10 0.51 0.5

50 50 0.51 0.5

Sample Output

0.50

0.60

0.88

Author

Speakless

Source

Gardon-DYGG Contest 2

---

十分典型的坑题，测试点里面有特别多的数据是坑你的。。。。害得我3次WA。

容易看出赢一次的概率为p(1-q)记为win，输一次的概率为q(1-p)记为lose，那么平一次的概率就是1-win-lose，记为tie。

记f(x)为有x个糖果时候的胜率，容易看出f(x)=win*f(x+1)+lose*f(x-1)+tie*f(x)。

接着，我居然尝试了递归——失败了。。。。。（←其实我觉得再改改也许能成功。）

这是个双向递推式，所以我们需要在上限和下限处各找到一个初值。根据题意f(0)=0,f(n+m)=1。（这个十分容易理解，你手上没有糖果的时候就必失败，手上存在全部糖果的时候就必胜。）

然后用RSolve查找通项。（←喂喂，这件事情好像比赛的时候没法干啊。）

这就解决了我会说？

哦，对了，实际上我们要求的其实是f(n)。

至于其他坑的地方，请见代码里面那多的不可直视的if else

AC代码：

//HDU 糖果大战 
#include <iostream> 
#include <cstdio> 
#include <cmath> 
using namespace std; 
double p,q; 
double result2(int n,int m); 
double result(int n,int m){ 
    double lose=(p-1)*q; 
    double win=(q-1)*p; 
    double bi=lose/win; 
    if(fabs(bi-1)<1e-8) return result2(n,m); 
    else return (pow(bi,n)-1)/(pow(bi,m+n)-1); 
} 
double result2(int n,int m){ 
    return (double)n/(n+m); 
} 
int main(int agrc, char *agrv[]){ 
    int N,M; 
    while(cin>>N>>M>>p>>q){ 
        if(N==0) cout<<"0.00"<<endl; 
        else if(M==0) cout<<"1.00"<<endl; 
        else if(fabs(p)<1e-8) cout<<"0.00"<<endl; 
        else if(fabs(q-1)<1e-8) cout<<"0.00"<<endl; 
        else if(fabs(p-q)<1e-8) printf("%.2fn",result2(N,M)); 
        else printf("%.2fn",result(N,M)); 
    } 
    return 0; 
} 

main