{"trustable":false,"sections":[{"title":"Description","value":{"format":"MD","content":" ![](CDN_BASE_URL/abbc1e585106e46f40c9e0f54755c644?v\u003d1720198314)\n\n你受雇于气候测量协会,这是一个科学组织,致力于长期跟踪全球天气趋势。当然,这并非易事。他们在世界各地部署了许多小型设备,旨在定期测量当地的天气状况。这些设备价格低廉,功能有限。\n\n每天,他们都会观察今天是四种标准天气中的哪一种,四种标准天气分别是:晴、阴、雨或frogs(下青蛙?foggy?)。每$n$天完成这些观察后,所有设备需要将结果报告给主服务器进行分析。然而,大量的设备发送检测结果将会导致可用的通信带宽超载。协会需要您的帮助,想出一种方法将这些报告压缩成更少的比特。\n\n对于不同位置的设备,您可以假设每天的检测天气是一个独立的随机事件,四种可能天气类型的预测概率是已知的。$4^n$种设备的所有可能的天气报告都必须编码为唯一的比特序列,这样任何序列都不是其他序列的前缀(否则服务器将不知道每个序列何时结束)。请你使用一种编码来最小化传输比特数的期望。"}},{"title":"Input","value":{"format":"MD","content":"The first line of input contains an integer $1 \\le n \\le 20$, the number of observations that go into each report. \n\nThe second line contains four positive floating-point numbers, $p_{\\text {sunny}}$, $p_{\\text {cloudy}}$, $p_{\\text {rainy}}$, and $p_{\\text {frogs}}$, representing the respective weather probabilities. \n\nThese probabilities have at most 6 digits after the decimal point and sum to 1."}},{"title":"Output","value":{"format":"MD","content":"Display the minimum expected number of bits in the encoding of a report, with an absolute or relative error of at most $10^{-4}$."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n0.9 0.049999 0.05 0.000001\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.457510\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e20\n0.25 0.25 0.25 0.25\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40.000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}