{"problem":{"name":"[THUPC 2023 决赛] 总投票数","description":{"content":"在关服前，运营发起了一系列投票，调查哪些游戏内容给玩家带来了更深的印象。 作为系列的忠实玩家，你想知道有多少人参加了关服前的投票，但是运营只公开了最终的投票结果：对于一项包含 $N$ 个选项的投票，选择第 $i$ 个选项的玩家比例为 $P_i$（$1\\le i\\le N$）。运营在公布结果时进行了四舍五入，所有的 $P_i$ 仅保留到小数点后第 $L$ 位。假设实际有 $K$ 位玩家参加了投票，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9380"},"statements":[{"statement_type":"Markdown","content":"在关服前，运营发起了一系列投票，调查哪些游戏内容给玩家带来了更深的印象。\n\n作为系列的忠实玩家，你想知道有多少人参加了关服前的投票，但是运营只公开了最终的投票结果：对于一项包含 $N$ 个选项的投票，选择第 $i$ 个选项的玩家比例为 $P_i$（$1\\le i\\le N$）。运营在公布结果时进行了四舍五入，所有的 $P_i$ 仅保留到小数点后第 $L$ 位。假设实际有 $K$ 位玩家参加了投票，其中有 $D_i$ 位玩家选择了第 $i$ 个选项，则应该有\n\n$$\nP_i-\\frac{1}{2}\\times 10^{-L}\\le\\frac{D_i}{K}< P_i+\\frac{1}{2}\\times 10^{-L}\n$$\n\n显然，所有的 $D_i$ 必须是非负整数，而 $K=\\sum_{i=1}^N D_i$ 则必须是正整数。现在，给定 $N$ 和 $P_i$，请你求出满足 $D_i$ 有非负整数解的最小的总投票数 $K$。\n\n## Input\n\n输入的第一行包含一个正整数 $N$，表示投票的选项总数。保证 $1\\le N\\le 100$。\n\n接下来 $N$ 行，每行包括一个 $[0, 1]$ 中的实数 $P_i$，表示选择第 $i$ 个选项的玩家比例。保证 $\\sum_{i=1}^N P_i =1$，所有 $P_i$ 均保留到小数点后第 $L$ 位，且 $1\\le L\\le 6$。\n\n## Output\n\n输出一个正整数，表示满足要求的最小总投票数 $K$。\n\n[samples]\n\n## Background\n\n各位亲爱的《La Lumière: Scarlet Intense Flame - Adventurous Scarlet -》玩家：\n\n非常荣幸能与您携手度过了这四年的美好时光，衷心感谢大家的支持与陪伴！\n\n现在，我们非常遗憾的宣布，《La Lumière: Scarlet Intense Flame - Adventurous Scarlet -》将于 2023 年 5 月 28 日 15:00 停止运营服务。\n\n停止运营相关时间表如下：\n\n……\n\n## Note\n\n**【样例解释 #1】**\n\n最小的总投票数为 $6$，对应每个选项的投票数为 $1, 2, 3$。\n\n**【样例解释 #2】**\n\n最小的总投票数为 $73$，对应每个选项的投票数为 $3, 8, 8, 12, 22, 5, 15$。\n\n**【样例解释 #3】**\n\n最小的总投票数为 $7766$，对应每个选项的投票数为 $12, 301, 123, 403, 629, 530, 1216, 808, 205, 1113, 1005, 1206, 215$。\n\n**【数据范围】**\n\n对于所有测试数据，$1\\le N\\le 100$，$0\\le P_i\\le 1$，$\\sum_{i=1}^N P_i=1$，且 $P_i$ 最多统一保留到小数点后 $6$ 位。\n\n**【题目来源】**\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。\n\n题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9380","tags":["数学","2023","O2优化","枚举","THUPC"],"sample_group":[["3\n0.166667\n0.333333\n0.500000\n","6\n"],["7\n0.041096\n0.109589\n0.109589\n0.164384\n0.301370\n0.068493\n0.205479\n","73\n"],["13\n0.00155\n0.03876\n0.01584\n0.05189\n0.08099\n0.06825\n0.15658\n0.10404\n0.02640\n0.14332\n0.12941\n0.15529\n0.02768\n","7766\n"]],"created_at":"2026-03-03 11:09:25"}}