糖果大战
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
Sample Output
0.50
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*(1-p))/(p*(1-q)); if(n==0)cout<<"0.00"<<endl; else if(m==0)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 ",(double)n/(m+n)); else { double an=(1-pow(k,n))/(1-pow(k,m+n)); printf("%.2lf ",an); } } }