Problem E: 翻硬币

Problem E: 翻硬币

Time Limit: 10 Sec  Memory Limit: 16 MB  Special Judge
Submit: 6  Solved: 6
[Submit][Status][Web Board]

Description

这是一个关于翻硬币的游戏。
在你的面前有 n 个硬币,从左到右排成一排。每个硬币上都标有分值。
当你抛任意一个硬币时,它有 prob/1,000,000,000 的概率正面朝上,否则反面朝上。
游戏进行的每一轮中,你必须进行如下操作:
1.  依次抛当前剩下的所有硬币。
2.  选择最左边的一枚正面朝上的硬币,如果都是反面朝上则选择第一枚硬币
3.  如果选中的硬币的两侧都有硬币,假设它们的分值分别是 L 和 R, 则本轮你获得 L*R 分。如果选中的硬币至少有一侧没有硬币,则本轮不得分。
4.  将选中的硬币拿走,将剩下的硬币排列整齐(不改变相对顺序)
 
当硬币都被拿走时,游戏结束。(换句话说,游戏进行 n 轮)
那么,这个游戏你的期望得分是多少呢?

Input

输入共包含三行:
第一行一个整数 n。
第二行n 个整数表示从左到右的硬币的分值。
第三行一个整数 prob
n<=300
硬币的分值 <= 1000
prob <= 1e9

Output

输出一行一个实数,代表期望得分,当相对误差或绝对误差不超过 1e-6 时,即为正确。

Sample Input

Input1:
3
2 3 4
500000000
 
Input2:
5
5 1 4 2 3
100000000
 
Input3:
5
1 1 1 1 1
1000000000

Sample Output

Output1:
2.0

Output2:
4.9853922048
 
Output3:
0.0

HINT

[Submit][Status]