P6915 [ICPC 2015 WF] Weather Report

 你被气候测量协会雇佣，这是一家对长期跟踪全球天气趋势感兴趣的科学组织。当然，这不是一项简单的任务。他们在世界各地部署了许多小型设备，旨在定期测量当地的天气状况。这些设备价格低廉，功能有所限制。每天它们会观察四种标准天气中的哪一种发生：晴天、多云、雨天或青蛙雨。在每进行 $n$ 次这样的观察后，结果会被报告给主服务器进行分析。然而，设备数量庞大导致可用通信带宽超载。协会需要你的帮助来想出一种方法，将这些报告压缩成更少的比特。 对于某个设备的位置，你可以假设每天的天气是一个独立的随机事件，并且你会得到四种可能天气类型的预测概率。设备的每一个 $4^n$ 种可能的天气报告必须被编码为一个唯一的比特序列，且没有序列是其他序列的前缀（这是一个重要的属性，否则服务器将不知道每个序列何时结束）。目标是使用一种编码，最小化传输比特的期望数量。

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

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

时间限制：1000 毫秒，内存限制：1048576 KB。 国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2015。 题面翻译由 ChatGPT-4o 提供。