首页 > 代码库 > UVA - 11021 Tribles (递推+概率)

UVA - 11021 Tribles (递推+概率)

2024-07-20 03:38:26   219人阅读

Description

Download as PDF

Problem A
Tribbles
Input: Standard Input

Output: Standard Output

GRAVITATION, n.
"The tendency of all bodies to approach one another with a strength
proportion to the quantity of matter they contain -- the quantity of
matter they contain being ascertained by the strength of their tendency
to approach one another. This is a lovely and edifying illustration of
how science, having made A the proof of B, makes B the proof of A."

Ambrose Bierce

You have a population of kTribbles. This particular species of Tribbles live for exactly one day and then die. Just before death, a single Tribble has the probabilityPi of giving birth to i more Tribbles. What is the probability that afterm 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 containingn (1<= n<=1000) , k (0<= k<=1000) and m (0<= m<=1000) . The nextn 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

4 
3 1 1
0.33 
0.34 
0.33 
3 1 2 
0.33 
0.34 
0.33 
3 1 2 
0.5 
0.0 
0.5 
4 2 2
0.5 
0.0 
0.0 
0.5
Case #1: 0.3300000 
Case #2: 0.4781370 
Case #3: 0.6250000 
Case #4: 0.3164062 
            

Problemsetter: Igor Naverniouk, EPS

Special Thanks: Joachim Wulff

题意：有k只麻球，每只活一天就会死亡，临死前可能会生出一些新的麻球，具体来说，生i个的概率是Pi，给定m，求m天后所有麻球均死亡的概率，注意，不是m天时就已全部死亡的情况也算在内

思路：每只麻球死亡是互不影响的，所以只需求出一开始只有1只麻球，m天后全部死亡的概率f(m)，由全概率公式，有：

   f(i) = p0+p1*f(i-1)+p2*f(i-1)^2+....pn-1*f(i-1)^n-1,其中pj*f(i-1)^j的含义是这个麻球生了j个后代，它们在i-1天后全部死亡，注意j个后代死亡是相互独立的，而每个死亡的概率都是f(i-1)，因此根据乘法公式，j个后代全部死亡的概率为f(i-1)^j，最后计算k只麻球就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1010;

int n, k, m;
double p[maxn], f[maxn];

int main() {
	int t, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &k, &m);
		for (int i = 0; i < n; i++)
			scanf("%lf", &p[i]);
		f[0] = 0, f[1] = p[0];
		for (int i = 2; i <= m; i++) {
			f[i] = 0;
			for (int j = 0; j < n; j++)
				f[i] += p[j] * pow(f[i-1], j); 
		}
		printf("Case #%d: %.7lf\n", cas++, pow(f[m], k));
	}
	return 0;
}



UVA - 11021 Tribles (递推+概率)


联系
我们