【cojs1487】麻球繁衍

2014年3月14日1,8960

【题目描述】

万有引力定律:

“使物体相互靠近的力的大小与物体的质量成正比——而物体的质量又由同一种力决定。这是一个有趣并且有益的例子,说明了科学是如何用A证明B,再用B证明A的。”——安布罗斯·比尔斯(美国讽刺作家——译者注)。

你有一坨K个毛球(<星际迷航>中的种族——译者注)。这种毛球只会存活一天。在死亡之前,一个毛球有P_i的概率生出i个毛球(i=0,1,…,n-1)。m天后所有毛球都死亡的概率是多少?(包含在第m天前全部死亡的情况)

【输入格式】

输入包含多组数据。

输入文件的第1行是一个正整数N,表示数据组数。

每组数据的第1行有3个正整数n(1<=n<=1000),k(0<=k<=1000),m(0<=m<=1000)。

接下来有n行,给出P_0,P_1,…,P_n-1。

【输出格式】

对于第i组数据,输出”Case #i: “,后面是第m天后所有毛球均已死亡的概率。

【样例输入】

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.3164063

【提示】

如果你的输出与标准答案相差不超过10^-5,那么你的答案就被认为是正确的。

【来源】

UVa11021 Tribles

刘汝佳,《算法竞赛入门经典训练指南》表2.8

题解

参看《算法竞赛入门经典训练指南》