Background

Execution.

This problem was originally called std::cout << std::fixed << std::setprecision(1) << 6.5 << '\n';.

[The picture deleted by the person involved.jpg]

【Upd 2023/04/15 21:42】A set of hack testdata was added in Subtask 2, #13. Now, in theory, all $\bm{50}$-point submissions during the contest can only get $\bm{30}$ points.

Problem Description

You are given $n$ decimal numbers $a_1 \dots a_n$.

For a number $a$, define its precision $f(a)$ as the smallest non-negative integer $k$ such that $10^k \times a$ is an integer. For an integer $a$, define $f(a) = 0$. For two decimal numbers $a, b$, define $g(a, b)$ as the minimum value of $f(c)$ over all numbers $c \in [\min(a,b), \max(a,b)]$.

For all $1 \leq i \leq n$, you need to compute and output the value of $\sum\limits_{j=1}^n g(a_i, a_j)$.

A decimal number is defined as a number that has an integer part and a fractional part, and whose fractional part is not $0$. The reason it is described in such a silly way is that the input guarantees every number has a decimal point, but it seems no matter how it is written, someone will complain. Sorry about that. So I still have to look at the picture deleted by the person involved. So if I write some nonsense here, can anyone see it.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain a decimal number $a_i$.

Output Format

Output $n$ lines. Each line contains an integer, representing the answer for $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

Hint

Constraints

This problem uses bundled tests.

Let $\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): No special constraints.

For all testdata, $0 \lt a_i \lt 10^9$, $1 \leq n \leq 10^5$, $1 \leq t \leq 3 \times 10^6$, it is guaranteed that $\bm{a_i}$ has no trailing $\color{black}\bm 0$, and it is not guaranteed that $\bm{a_i}$ are pairwise distinct.

Sample Explanation

Take $i = 1$ as an example:

• $j = 1$: take $c = 11.4514$, $f(c) = 4$.
• $j = 2$: take $c = 11.46$, $f(c) = 2$.
• $j = 3$: take $c = 11.2$, $f(c) = 1$.
• $j = 4$: take $c = 11.3$, $f(c) = 1$.
• $j = 5$: take $c = 11.47$, $f(c) = 2$.

Therefore, $\sum\limits_{j=1}^n g(a_1, a_j) = 4 + 2 + 1 + 1 + 2 = 10$. For the same $j$, among all the $c$ given above, there may also be other different $c$ such that $f(c)$ is also minimal.

Translated by ChatGPT 5