问题陈述

设 $N$ 是一个正奇数。

有 $N$ 枚硬币，编号为 $1, 2, \ldots, N$ 。对于每个 $i$ ( $1 \leq i \leq N$ )，当抛掷编号为 $i$ 的硬币时，正面出现的概率为 $p_i$ ，反面出现的概率为 $1 - p_i$ 。

太郎抛出了所有的 $N$ 枚硬币。求正面比反面多的概率。

限制因素

• $N$ 是奇数。
• $1 \leq N \leq 2999$
• $p_i$ 是实数，且有两位小数。
• $0 \lt p_i \lt 1$

输入

输入内容由标准输入法提供，格式如下：

• $N$
• $p_1$ $p_2$ $\ldots$ $p_N$

输出

打印正面多于反面的概率。如果绝对误差不大于 $10^{-9}$ ，则认为输出正确。

3
0.30 0.60 0.80

0.612

正面多于反面的概率如下：

• 出现 $(Coin 1, Coin 2, Coin 3) = (Head, Head, Head)$ 的概率是 $0.3 × 0.6 × 0.8 = 0.144$ ；
• 出现 $(Coin 1, Coin 2, Coin 3) = (Tail, Head, Head)$ 的概率是 $0.7 × 0.6 × 0.8 = 0.336$ ；
• 拥有 $(Coin 1, Coin 2, Coin 3) = (Head, Tail, Head)$ 的概率是 $0.3 × 0.4 × 0.8 = 0.096$ ；
• 有 $(Coin 1, Coin 2, Coin 3) = (Head, Head, Tail)$ 的概率是 $0.3 × 0.6 × 0.2 = 0.036$ 。

因此，正面比反面多的概率是 $0.144 + 0.336 + 0.096 + 0.036 = 0.612$ 。

1
0.50

0.5

0.500、0.500000001 和 0.499999999 等输出也被认为是正确的。

5
0.42 0.01 0.42 0.99 0.42

0.3821815872

来源

https://atcoder.jp/contests/dp/tasks/dp_i