糖果大战
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1855 Accepted Submission(s): 613
Problem Description
生日Party结束的那天晚上，剩下了一些糖果，Gandon想把所有的都统统拿走，Speakless于是说：“可以是可以，不过我们来玩24点，你不是已经拿到了一些糖果了吗？这样，如果谁赢一局，就拿走对方一颗糖，直到拿完对方所有的糖为止。”如果谁能算出来而对方算不出来，谁就赢，但是如果双方都能算出或者都不能，就算平局，不会有任何糖果的得失。
Speakless是个喜欢提前想问题的人，既然他发起了这场糖果大战，就自然很想赢啦（不然可就要精光了-_-）。现在他需要你的帮忙，给你他每局赢的概率和Gardon每局赢的概率，请你给出他可能获得这场大战胜利的概率。
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
10 10 0.51 0.5
50 50 0.51 0.5
Sample Output
0.50
0.60
0.88
0.60
0.88
Author
Speakless
我们用Xt表示t时刻S君手中的糖果数, 则{Xt,t=0, 1, 2.....}是一个Markov Chain. 其状态转移概率为
P00=PNN=1, 这里N = m+n
Pi, i+1=p(1-q), Pi, i-1=(1-p)q, Pi, i=1-p(1-q)-q(1-p), i=1, 2, 3...., N-1; (*)
该MC的状态有3类{0}, {1, 2, ..., N-1}, 以及{N}, 其中第二类是非常返的, 第一三类是常返的, 因为每个一非常返态通常仅到达有穷多次, 所以在进行可以在进行有穷多次博弈后, S君或者最终赢得所有糖果, 或者输掉所有糖果.
这里我们的定义fi=fiN=Pr(S君经过有限次博弈赢得N个糖果|X0=i), 这里fi是一个条件概率, 就是开始的时候有i个糖果, 最中赢得N个糖果的概率. 从(*)式可以知道, 当我们有在某时刻t有i个糖果, 我们可以有三种途径可以最终赢得N个糖果. 1. 赢得一个糖果, 概率是p(1-q), 这是下一个时刻t+1G君就有了i+1个糖果. 2. 输掉比赛, 在下一个时刻变成了i-1个糖果, 概率是q(1-p). 3. 打成平手, 下一个时刻还有i个糖果, 概率是1-p(1-q)-q(1-p). 这样我么就可以得到如下公式
fi=p(1-q)*fi+1+q(1-p)*fi-1+(1-p(1-q)-q(1-p))*fi
令 P=p(1-q), Q=q(1-p), K=Q/P, 则
fi+1-fi=K(fi-fi-1)
fi+1-fi是简单的等比数列, 则 fi+1-fi=Ki(f1-f0). 注意到fN=1, f0=0, 这里N=m+n;
f2-f1=Kf1
f3-f2=K2f1
................
fn-fn-1=Kn-1f1
..............
fm+n-fm+n-1=Km+n-1f1
相加一下, fn=(1+K+K2+...+Kn-1)f1, fn+m=(1+K+K2+...+Km+n-1)f1
所以fn=(1+K+K2+...+Kn-1)/(1+K+K2+...+Km+n-1), k!=1时, 可以化简为fn=(1-Kn)/(1-Km+n)
http://friends119119.blog.163.com/blog/static/12434199520100299446587/
P00=PNN=1, 这里N = m+n
Pi, i+1=p(1-q), Pi, i-1=(1-p)q, Pi, i=1-p(1-q)-q(1-p), i=1, 2, 3...., N-1; (*)
该MC的状态有3类{0}, {1, 2, ..., N-1}, 以及{N}, 其中第二类是非常返的, 第一三类是常返的, 因为每个一非常返态通常仅到达有穷多次, 所以在进行可以在进行有穷多次博弈后, S君或者最终赢得所有糖果, 或者输掉所有糖果.
这里我们的定义fi=fiN=Pr(S君经过有限次博弈赢得N个糖果|X0=i), 这里fi是一个条件概率, 就是开始的时候有i个糖果, 最中赢得N个糖果的概率. 从(*)式可以知道, 当我们有在某时刻t有i个糖果, 我们可以有三种途径可以最终赢得N个糖果. 1. 赢得一个糖果, 概率是p(1-q), 这是下一个时刻t+1G君就有了i+1个糖果. 2. 输掉比赛, 在下一个时刻变成了i-1个糖果, 概率是q(1-p). 3. 打成平手, 下一个时刻还有i个糖果, 概率是1-p(1-q)-q(1-p). 这样我么就可以得到如下公式
fi=p(1-q)*fi+1+q(1-p)*fi-1+(1-p(1-q)-q(1-p))*fi
令 P=p(1-q), Q=q(1-p), K=Q/P, 则
fi+1-fi=K(fi-fi-1)
fi+1-fi是简单的等比数列, 则 fi+1-fi=Ki(f1-f0). 注意到fN=1, f0=0, 这里N=m+n;
f2-f1=Kf1
f3-f2=K2f1
................
fn-fn-1=Kn-1f1
..............
fm+n-fm+n-1=Km+n-1f1
相加一下, fn=(1+K+K2+...+Kn-1)f1, fn+m=(1+K+K2+...+Km+n-1)f1
所以fn=(1+K+K2+...+Kn-1)/(1+K+K2+...+Km+n-1), k!=1时, 可以化简为fn=(1-Kn)/(1-Km+n)
http://friends119119.blog.163.com/blog/static/12434199520100299446587/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define eps 0.001
using namespace std;
int main()
{
int n,m;
double p,q;
while(cin>>n>>m>>p>>q)
{
double k=(q*(-p))/(p*(-q));
if(n==)cout<<"0.00"<<endl;
else
if(m==)cout<<"1.00"<<endl;
else
if(fabs(p)<eps||fabs(q-1.0)<eps)cout<<"0.00"<<endl;
else
if(fabs(p-1.0)<eps||fabs(q)<eps)cout<<"1.00"<<endl;
else
if(fabs(k-1.0)<eps)printf("%.2lf\n",(double)n/(m+n));
else {
double an=(-pow(k,n))/(-pow(k,m+n));
printf("%.2lf\n",an);
}
}
}