1010 - 动态规划:期望DP:朝上或朝下
Time Limit : 1 秒
Memory Limit : 256 MB
有这么个玩法: 在每一轮中,孩子们将手朝上(白色)或者朝下(黑色)。 如果所有的孩子做出相同的选择,只有一个例外,那么那个例外的孩子将会被淘汰。 游戏重复进行,直到只剩下两个孩子停止。 每个孩子有一个固定的概率独立选择是否将手朝上。 给定n个孩子的概率,请输出游戏期望回合数是多少。
Input
第一行为正整数n,n不超过20,表示孩子数量。 接下来n行,每行一个数字pi表示孩子i的概率,0.1≤pi≤0.9。
Output
输出一个数字表示期望回合数。 注意:输出结果与标准结果的绝对误差或者相对误差小于10^-6即视为正确。
Examples
Input
3 0.5 0.5 0.5
Output
1.3333333
Input
5 0.1 0.3 0.5 0.7 0.9
Output
7.4752846