[UVA] 12457 - Tennis contest
| D: Tennis contest |
Background
Nadal or Djokovic? Who is the best one?
The Problem
The two most famous tennis players, A and B, are facing each other in up to 2n-1 matches. The one who wins n matches will be the best player in the world. We supose the result of each game doesn't depend on the rest, and there is a constant likelihood, p, of A to win a match. Draw is an invalid result. Which is in advance the probability of A to win the title?
The Input
The first line of the input contains an integer, t, indicating the number of test cases. For each test case, two lines appear, the first one contains a number n, 1<=n<=25, representing the number of wins A has to reach. The second line contains a number p, 0<=p<=1, representing the probability of A to win a match.
The Output
For each test case the output should contain a single line with the number representing the probability in advance of A to win the title of best player in the world.
Sample Input
5 25 0.5 25 0.4 25 0.6 15 0.8 10 0.95
Sample Output
0.50 0.08 0.92 1.00 1.00
OMP'12
Facultad de Informatica
Universidad de Murcia (SPAIN)
給定 A 單場贏 B 的機率為 p, 先贏 n 場的人獲勝，問 A 最後贏的機率為何？
題目解法：
設 dp[i][j] 表示 A 贏 i 場, B 贏 j 場，進行轉移。
轉移的時候，如果 i == n or j == n 則忽略不計，由於遊戲已經結束。
最後 result = sigma(dp[n][i])
#include <stdio.h>
#include <math.h>
int main() {
int testcase;
int n, i, j, k;
double p;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %lf", &n, &p);
double dp[55][55] = {};
dp[0][0] = 1;
for(i = 0; i <= n; i++) {
for(j = 0; j <= n; j++) {
if(i == n || j == n) continue;
dp[i+1][j] += dp[i][j]*p;
dp[i][j+1] += dp[i][j]*(1-p);
}
}
double ret = 0;
for(i = 0; i <= n; i++)
ret += dp[n][i];
printf("%.2lf\n", ret);
}
return 0;
}