Problem Background

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

We are honored to have spent these four wonderful years with you, and we sincerely thank you for your support and companionship!

It is with great regret that we announce the cessation of service for "La Lumière: Scarlet Intense Flame - Adventurous Scarlet -" on May 28, 2023, at 15:00.

The schedule for the cessation of operations is as follows:

...

Problem Description

Before the shutdown, the operation team initiated a series of votes to survey which game content left a deeper impression on the players.

As a loyal player of the series, you want to know how many people participated in the votes before the shutdown, but the operation team only disclosed the final voting results: for a vote with $N$ options, the proportion of players who chose the $i$-th option is $P_i$ ($1 \le i \le N$). The operation team rounded the results, and all $P_i$ are only retained to $L$ decimal places. Assuming that $K$ players participated in the vote, with $D_i$ players choosing the $i$-th option, then it should hold that

$$ 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$ that satisfies $D_i$ has non-negative integer solutions.

Input Format

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

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

Output Format

Output a positive integer representing the smallest total number of votes $K$ that meets the requirements.

Sample Input and Output

Sample Input #1

3
0.166667
0.333333
0.500000

Sample Output #1

6

Sample Input #2

7
0.041096
0.109589
0.109589
0.164384
0.301370
0.068493
0.205479

Sample Output #2

73

Sample Input #3

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

Sample Output #3

7766

Notes

[Sample Explanation #1]

The smallest total number of votes is $6$, corresponding to the number of votes for each option being $1, 2, 3$.

[Sample Explanation #2]

The smallest total number of votes is $73$, corresponding to the number of votes for each option being $3, 8, 8, 12, 22, 5, 15$.

[Sample Explanation #3]

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

[Data Range]

For all test data, $1 \le N \le 100$, $0 \le P_i \le 1$, $\sum_{i=1}^N P_i = 1$, and $P_i$ is uniformly retained to at most $6$ decimal places.

[Problem Source]

From the 2023 Tsinghua University Student Programming Contest and University Invitational Tournament (THUPC2023) Finals.

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

见题面 Input 部分

见题面 Output 部分