#P18821. [Croatian CPC2016] Vjerojatnost

[Croatian CPC2016] Vjerojatnost

[Croatian CPC2016] Vjerojatnost

题目描述

Perica 正在玩一个字母游戏。屏幕下方有 nn 个从左到右排列的格子,最初全部为空。

游戏会依次生成 nn 个字母。每个字母都从 A、B、C、D 中随机选择,各次选择相互独立,四种字母出现的概率固定。

每出现一个字母,Perica 必须立即将它放入一个尚未被占用的格子。放下后不能移动,也不能等待后面的字母出现后再决定当前位置。策略可以根据已经出现的字母和当前局面作出选择。

所有格子都被填满后,如果字母从左到右按字母表顺序非递减排列,Perica 就获胜。

给定四种字母出现的概率,求 Perica 采用最优策略时获胜的概率。

输入格式

第一行包含一个正整数 nn(n≤250n\le250)。

第二行包含四个整数 a,b,c,da,b,c,d(0≤a,b,c,d≤1000\le a,b,c,d\le100,a+b+c+d=100a+b+c+d=100),分别表示 A、B、C、D 出现的百分比概率。

输出格式

输出一个实数,表示最优策略下的获胜概率。

你的答案与标准答案的绝对误差或相对误差不超过 10−610^{-6} 即视为正确。

样例 1

输入

3
25 25 25 25

输出

0.75

样例 2

输入

10
0 50 0 50

输出

1

样例 3

输入

5
10 20 30 40

输出

0.62116