{"problem":{"name":"「TAOI-1」Apollo","description":{"content":"给出 $n$ 个十进制小数 $a_1 \\dots a_n$。 对于一个 **数** $a$，定义其精度 $f(a)$ 表示最小的非负整数 $k$ 使得 $10^k\\times a$ 为整数；对于整数 $a$，定义 $f(a) = 0$。对于两个十进制小数 $a, b$，定义 $g(a, b)$ 为对于所有 **数** $c \\in [\\min(a,b), \\max(a,b)]$ 的 $f(c)$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9218"},"statements":[{"statement_type":"Markdown","content":"给出 $n$ 个十进制小数 $a_1 \\dots a_n$。\n\n对于一个 **数** $a$，定义其精度 $f(a)$ 表示最小的非负整数 $k$ 使得 $10^k\\times a$ 为整数；对于整数 $a$，定义 $f(a) = 0$。对于两个十进制小数 $a, b$，定义 $g(a, b)$ 为对于所有 **数** $c \\in [\\min(a,b), \\max(a,b)]$ 的 $f(c)$ 的最小值。\n\n对于所有 $1 \\leq i \\leq n$，你需要求出 $\\sum\\limits_{j=1}^ng(a_i, a_j)$ 的值并输出。\n\n定义十进制小数是一个含有整数部分和小数部分的数，其小数部分不为 $0$。之所以描述得这么愚蠢是因为保证输入的每个数都有小数点，但是好像无论什么写法都会有人提出不满，真是抱歉了。~~所以还是得看看被当事人删掉的图片。所以我在这里写闲话有人看得到吗。~~\n\n## Input\n\n第一行一个整数 $n$。\n\n接下来 $n$ 行，每行一个十进制小数 $a_i$。\n\n## Output\n\n$n$ 行，每行一个整数，分别表示 $i = 1 \\dots n$ 对应的答案。\n\n[samples]\n\n## Background\n\nExecution.\n\n这题原来叫 `std::cout << std::fixed << std::setprecision(1) << 6.5 << '\\n';`。\n\n[被当事人删掉的图片.jpg]\n\n**【Upd 2023/04/15 21:42】添加了一组 Hack 数据位于 Subtask 2，#13。现在所有赛时的 $\\bm{50}$ 分提交理论上均只能获得 $\\bm{30}$ 分。**\n\n## Note\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n令 $\\sum\\limits_{i=1}^n f(a_i) = t$。\n\n- Subtask 1（15 points）：$a_i \\leq 10$，$n \\leq 5$，$t \\leq 10$。\n- Subtask 2（15 points）：$a_i \\leq 10$，$n \\leq 100$，$t \\leq 1000$。\n- Subtask 3（20 points）：$n \\leq 1722$。\n- Subtask 4（15 points）：$a_i \\leq 1$。\n- Subtask 5（35 points）：无特殊限制。\n\n对于所有数据，$0 \\lt a_i \\lt 10^9$，$1 \\leq n \\leq 10^5$，$1 \\leq t \\leq 3 \\times 10^6$，**保证 $\\bm{a_i}$ 没有后导 [$\\color{black}\\bm 0$](https://cdn.luogu.com.cn/upload/image_hosting/pg66fm1z.png)，不保证 $\\bm{a_i}$ 互不相同**。\n\n### 样例解释\n\n以 $i = 1$ 为例：\n\n+ $j = 1$：取 $c = 11.4514$，$f(c) = 4$；\n+ $j = 2$：取 $c = 11.46$，$f(c) = 2$；\n+ $j = 3$：取 $c = 11.2$，$f(c) = 1$；\n+ $j = 4$：取 $c = 11.3$，$f(c) = 1$；\n+ $j = 5$：取 $c = 11.47$，$f(c) = 2$。\n\n故 $\\sum\\limits_{j=1}^n g(a_1, a_j) = 4 + 2 + 1 + 1 + 2 = 10$。对于同一个 $j$，上文给出的所有 $c$，都可能有其它的不同的 $c$ 满足 $f(c)$ 同样最小。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9218","tags":["O2优化","最近公共祖先 LCA","进制","字典树 Trie","单调栈"],"sample_group":[["5\n11.4514\n11.4778\n11.1338\n11.1236\n11.4789","10\n11\n9\n9\n11"],["8\n1.1145\n1.114\n1.1145\n1.514\n1.19198\n1.1154\n1.114\n1.1145","24\n21\n24\n10\n18\n22\n21\n24"]],"created_at":"2026-03-03 11:09:25"}}