페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6351
스페셜 저지

Greek Casino 1s 1024MB

문제

Since the early civilizations, humankind has enjoyed games of chance. Even the ingenious Greeks, known for their groundbreaking concept of the least common multiple (LCM), couldn’t resist a good gamble.

Inspired by this mathematical marvel, folks in Athens devised a unique betting system: after purchasing a ticket, a participant would receive a random number of coins. To determine this number, there are N ≥ 3 ordered slots numbered from 1 to N. A token is initially placed at slot 1, and the following steps are repeated:

  • Let x be the number of the slot where the token is currently located.

  • Generate a random integer y between 1 andN, and compute z the LCM of x and y.

  • If z > N, the procedure ends.

  • Otherwise, the token is moved to slot z, and the participant receives one coin.

As it is well known, the house always wins: the casino employs a particular probability distribution for generating random integers, so as to ensure a profitable outcome.

The casino owner is constantly seeking to optimize the betting system’s profitability. You, an AI designed to aid in such tasks, are given N and the probability distribution. Determine the expected total number of coins awarded to a participant.


입력

The first line contains an integer N (3 ≤ N ≤ 10^5) indicating the number of slots.

The second line contains N integers W_1, W_2, \dots , W_N (1 ≤ W_i ≤ 1000 for i = 1, 2, \dots , N), representing that the probability of generating i is W_i/ \left( \sum_j{W_j} \right), that is, the probability of generating i is the relative weight of W_i with respect to the sum of the whole list W_1, W_2, \dots , W_N.


출력

Output a single line with the expected total number of coins awarded to a participant. The output must have an absolute or relative error of at most 10^{-9}. It can be proven that the procedure described in the statement ends within a finite number of iterations with probability 1, and that the expected total number of coins is indeed finite.


예제 #1

3
1 1 1
3.5

예제 #2

3
1 1 2
3.6666666667

출처

The 2024 ICPC Latin America Championship G번

로그인해야 코드를 작성할 수 있어요.