Description

你被气候测量协会雇佣，这是一家对长期跟踪全球天气趋势感兴趣的科学组织。当然，这不是一项简单的任务。他们在世界各地部署了许多小型设备，旨在定期测量当地的天气状况。这些设备价格低廉，功能有所限制。每天它们会观察四种标准天气中的哪一种发生：晴天、多云、雨天或青蛙雨。在每进行 $n$ 次这样的观察后，结果会被报告给主服务器进行分析。然而，设备数量庞大导致可用通信带宽超载。协会需要你的帮助来想出一种方法，将这些报告压缩成更少的比特。

对于某个设备的位置，你可以假设每天的天气是一个独立的随机事件，并且你会得到四种可能天气类型的预测概率。设备的每一个 $4^n$ 种可能的天气报告必须被编码为一个唯一的比特序列，且没有序列是其他序列的前缀（这是一个重要的属性，否则服务器将不知道每个序列何时结束）。目标是使用一种编码，最小化传输比特的期望数量。

Input Format

输入的第一行包含一个整数 $1 \le n \le 20$，表示每个报告中的观察次数。第二行包含四个正浮点数，$p_{\text {sunny}}$，$p_{\text {cloudy}}$，$p_{\text {rainy}}$ 和 $p_{\text {frogs}}$，表示各自的天气概率。这些概率小数点后最多有 6 位数字，并且总和为 1。

Output Format

显示报告编码中比特的最小期望数量，绝对误差或相对误差最多为 $10^{-4}$。

2
0.9 0.049999 0.05 0.000001

1.457510

20
0.25 0.25 0.25 0.25

40.000000

Hint

时间限制：1000 毫秒，内存限制：1048576 KB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2015。

题面翻译由 ChatGPT-4o 提供。