hdu 1204糖果大战
阅读量:
searchstar
2019-11-06 11:58:26
Categories：
Tags：
题意：A有n个糖果，B有m个糖果，他们玩24点游戏，A能解答出来的概率是p，B能解答出来的概率是q，如果都解答出来或都没解答出来就平局，否则如果A解答出来了，B给A一颗糖，否则A给B一颗糖，某一方糖全部给光结束。求A赢的概率。
下面记pa = p(1-q)为A赢的概率，pb =
q(1-p)为B赢的概率，(1-pa-pb)为平局的概率。
设f(i)为A有i个糖果时赢的概率，则
f(i) = pa * f(i+1) + pb * f(i−1) + (1−pa−pb) * f(i)
pa * (f(i+1)−f(i)) = pb * (f(i)−f(i−1))
如果n == 0，则f(n) = 0
否则如果m == 0，则f(n) = 1
(n == 0且m == 0题目没有定义，假装没有)
否则如果pa = 0，则f(n) = 0
设g(i) = f(i+1) − f(i)，则
g(i)/g(i−1) = pb/pa
记t = pb/pa
则g(i) = tg(i−1)
g(0) + g(1) + ⋯ + g(n+m−1) = f(n+m) − f(0) = 1
因为f(n+m) = 1, f(0) = 0
如果t ≠ 1，
所求
如果t = 1，
g(0)(1+t+⋯+tn + m − 1) = g(0)(n+m) = 1
代码：
#include <cstdio>
#include <cmath>
using namespace std;
double eps = 1e-8;
int sgn(double x) {
return x < -eps ? -1 : (x > eps ? 1 : 0);
}
int main() {
double n, m;
double p, q;
while (~scanf("%lf%lf%lf%lf", &n, &m, &p, &q)) {
if (sgn(n) == 0) {
puts("0.00");
} else if (sgn(m) == 0) {
puts("1.00");
} else {
double pb = q * (1 - p), pa = (p * (1 - q));
if (sgn(pa) == 0) {
puts("0.00");
} else if (sgn(pb) == 0) {
puts("1.00");
} else {
double t = pb / pa;
if (sgn(t - 1)) {
printf("%.2f\n", (pow(t, n) - 1) / (pow(t, n + m) - 1));
} else {
printf("%.2f\n", n / (n + m));
}
}
}
}
return 0;
}
|