题目背景

Execution.

这题原来叫 std::cout << std::fixed << std::setprecision(1) << 6.5 << '\n';。

[被当事人删掉的图片.jpg]

【Upd 2023/04/15 21:42】添加了一组 Hack 数据位于 Subtask 2，#13。现在所有赛时的 $\bm{50}$ 分提交理论上均只能获得 $\bm{30}$ 分。

题目描述

给出 $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)$ 的最小值。

对于所有 $1 \leq i \leq n$，你需要求出 $\sum\limits_{j=1}^ng(a_i, a_j)$ 的值并输出。

定义十进制小数是一个含有整数部分和小数部分的数，其小数部分不为 $0$。

输入格式

从标准输入中读入数据。

第一行一个整数 $n$。

接下来 $n$ 行，每行一个十进制小数 $a_i$。

输出格式

输出到标准输出。

$n$ 行，每行一个整数，分别表示 $i = 1 \dots n$ 对应的答案。

5
11.4514
11.4778
11.1338
11.1236
11.4789

10
11
9
9
11

8
1.1145
1.114
1.1145
1.514
1.19198
1.1154
1.114
1.1145

24
21
24
10
18
22
21
24

提示

数据范围

本题采用捆绑测试。

令 $\sum\limits_{i=1}^n f(a_i) = t$。

• Subtask 1（15 points）：$a_i \leq 10$，$n \leq 5$，$t \leq 10$。
• Subtask 2（15 points）：$a_i \leq 10$，$n \leq 100$，$t \leq 1000$。
• Subtask 3（20 points）：$n \leq 1722$。
• Subtask 4（15 points）：$a_i \leq 1$。
• Subtask 5（35 points）：无特殊限制。

对于所有数据，$0 < a_i < 10^9, 1 \leq n \leq 10^5, 1 \leq t \leq 3 \times 10^6$，保证 $\bm{a_i}$ 没有后导 $\color{black}\bm 0$，不保证 $\bm{a_i}$ 互不相同。

样例解释

以 $i = 1$ 为例：

• $j = 1$：取 $c = 11.4514$，$f(c) = 4$；
• $j = 2$：取 $c = 11.46$，$f(c) = 2$；
• $j = 3$：取 $c = 11.2$，$f(c) = 1$；
• $j = 4$：取 $c = 11.3$，$f(c) = 1$；
• $j = 5$：取 $c = 11.47$，$f(c) = 2$。

故 $\sum\limits_{j=1}^n g(a_1, a_j) = 4 + 2 + 1 + 1 + 2 = 10$。对于同一个 $j$，上文给出的所有 $c$，都可能有其它的不同的 $c$ 满足 $f(c)$ 同样最小。