Background

Dear players of La Lumière: Scarlet Intense Flame - Adventurous Scarlet -:

It has been a great honor to spend these four wonderful years with you. We sincerely thank everyone for your support and companionship.

Now, we regret to announce that La Lumière: Scarlet Intense Flame - Adventurous Scarlet - will stop operating at 15:00 on May 28, 2023.

The shutdown schedule is as follows:

……

Problem Description

Before the shutdown, the operators launched a series of polls to find out which game content left a deeper impression on players.

As a loyal player of the series, you want to know how many people participated in the polls before the shutdown. However, the operators only made the final poll results public: for a poll with $N$ options, the proportion of players who chose option $i$ is $P_i$ ($1 \le i \le N$). When publishing the results, the operators rounded the numbers, and each $P_i$ is kept to the $L$-th digit after the decimal point. Suppose in reality there are $K$ players participating in the poll, and $D_i$ players chose option $i$. Then we should have

$$P_i-\frac{1}{2}\times 10^{-L}\le\frac{D_i}{K}< P_i+\frac{1}{2}\times 10^{-L}$$

Clearly, all $D_i$ must be non-negative integers, and $K=\sum_{i=1}^N D_i$ must be a positive integer. Now, given $N$ and $P_i$, please find the smallest total number of votes $K$ such that $D_i$ has a non-negative integer solution.

Input Format

The first line contains a positive integer $N$, indicating the total number of options in the poll. It is guaranteed that $1 \le N \le 100$.

The next $N$ lines each contain a real number $P_i$ in $[0, 1]$, indicating the proportion of players who chose option $i$. It is guaranteed that $\sum_{i=1}^N P_i = 1$. All $P_i$ are kept to the $L$-th digit after the decimal point, and $1 \le L \le 6$.

Output Format

Output a positive integer, indicating the minimum total number of votes $K$ that satisfies the requirements.

3
0.166667
0.333333
0.500000

6

7
0.041096
0.109589
0.109589
0.164384
0.301370
0.068493
0.205479

73

13
0.00155
0.03876
0.01584
0.05189
0.08099
0.06825
0.15658
0.10404
0.02640
0.14332
0.12941
0.15529
0.02768

7766

Hint

[Sample Explanation #1]

The minimum total number of votes is $6$, and the corresponding votes for each option are $1, 2, 3$.

[Sample Explanation #2]

The minimum total number of votes is $73$, and the corresponding votes for each option are $3, 8, 8, 12, 22, 5, 15$.

[Sample Explanation #3]

The minimum total number of votes is $7766$, and the corresponding votes for each option are $12, 301, 123, 403, 629, 530, 1216, 808, 205, 1113, 1005, 1206, 215$.

[Constraints]

For all testdata, $1 \le N \le 100$, $0 \le P_i \le 1$, $\sum_{i=1}^N P_i = 1$, and all $P_i$ are kept uniformly to at most $6$ digits after the decimal point.

[Source]

From the finals of the 2023 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2023).

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5