[Wf2015]Weather Report

时间限制:2s      空间限制:128MB

题目描述

我们假设每天只会出现四种天气:晴朗,多云,大雨,大雾,并已经预测了这四种天气每天出现的概率。现在我们要传输未来n天的天气状况。为了减轻传输压力,我们通过对n天所有4^n种可能的天气状况进行二进制编码来进行传输,并且不存在一个天气状况的编码是另外某一个编码的前缀。我们希望用某种编码方式来使将要传输的二进制位数的期望值最小。


输入格式

第一行包含一个整数n(1≤n≤20),表示将要传输未来n天的天气状况。
第二行包含四个和为1的实数,代表每天四种天气出现的概率。输入的每个实数最多精确到小数点后6位。


输出格式

输出最小期望传输的二进制位数,绝对误差或相对误差不超过1e-4。


样例输入

2
0.9 0.049999 0.05 0.000001

样例输出

1.457510

提示

Sample input 2

20
0.25 0.25 0.25 0.25

Sample output 2

40.000000


题目来源

鸣谢phile提供译文