[UVA] 11021 - Tribles
Problem A
Tribbles
Input: Standard Input
Output: Standard Output
|
GRAVITATION, n. |
Ambrose Bierce
You have a population of k Tribbles. This particular species of Tribbles live for exactly one day and then die. Just before death, a single Tribble has the probability Pi of giving birth to i more Tribbles. What is the probability that after m generations, every Tribble will be dead?
Input
The first line of input gives the number of cases, N.
N test cases follow. Each one starts with a line containing n (1<=n<=1000),
k (0<=k<=1000) and m (0<=m<=1000).
The next n lines will give the probabilities P0, P1, ..., Pn-1.
Output
For each test case, output one line containing "Case #x:"
followed by the answer, correct up to an absolute or relative error of 10-6.
|
Sample Input |
Sample Output |
43 1 10.330.340.333 1 20.330.340.333 1 20.50.00.54 2 20.50.00.00.5 |
Case #1: 0.3300000Case #2: 0.4781370Case #3: 0.6250000Case #4: 0.3164062 |
Problemsetter: Igor Naverniouk, EPS
Special Thanks: Joachim Wulff
有一種生物，生完下一代就會滅亡，也有可能不生就滅亡。
根據機率 Pi 產生 i 個子代。假使一開始有 k 隻這種生物，問剛好在第 m 代絕種的機率為何。
題目解法：
一開始的 k 隻，差別只在於次方，因此只先考慮 1 隻起頭。
假設 dp[i] 為只有 1 隻起頭的情況下，在第 i 代絕種的機率。
打算窮舉第一代的情況 dp[i] += p[j]*pow(dp[i-1], j)
即第一代如果根據機率 pj 產生 j 隻的情況下，其中一隻的後代必須存活 i-1 代，
而當 j 越大，絕種的機率當然成指數下降。
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
double dp[1005], p[1005];
int main() {
int testcase, cases = 0;
int N, K, M;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
int N, K, M;
scanf("%d %d %d", &N, &K, &M);
for(i = 0; i < N; i++)
scanf("%lf", &p[i]);
dp[0] = 0;
for(i = 1; i <= M; i++) {
dp[i] = 0;
for(j = 0; j < N; j++)
dp[i] += p[j]*pow(dp[i-1], j);
}
printf("Case #%d: %.7lf\n", ++cases, pow(dp[M], K));
}
return 0;
}