No.1151 Challenge Game
タグ : / 解いたユーザー数 51
作問者 :
Kiri8128
/ テスター :
theory_and_me
Problem Statement
null and kiri play a challenge game.
Initially there are $N$ cards, and the $i\ (1\le i\le N)$-th card has a positive integer $A_i$ written on it.
Initially, both null and kiri have a score of 0 points.
Starting with null, they alternately perform the following operation.
- Choose one card that has not been removed yet and "challenge" it.
- If the integer written on the chosen card is $a$, the challenge succeeds with probability $\displaystyle\frac{1}{a}$.
- If the challenge succeeds, the card is removed and $a$ points are added to the score of the player who made the challenge.
- If the challenge fails, the card is not removed and the scores do not change.
- Whether the challenge succeeds or fails, the player's turn ends and it becomes the opponent's turn.
Input
$N$ $A_1\ A_2\ \cdots A_N$
$1\le N\le 10$
$1\le A_i\le 20\ (1\le i\le N)$
Output
Output the answer on one line.
Print a newline at the end.
Your answer is considered correct if the absolute or relative error is at most $10^{-6}$.
It can be shown that, under the constraints of this problem, the probability in question is uniquely determined.
Sample
Sample 1
Input
2 1 2
Output
0.6666666667
There are 2 cards, and whoever takes the card with 2 written on it wins.
As long as the 2 card remains, aiming for the 2 is optimal. The success rate when challenging the 2 card is $\displaystyle\frac12$.
The probability that null wins is $\displaystyle\frac{1}{2} + (\frac{1}{2})^3 + (\frac{1}{2})^5 + \cdots = \frac{2}{3}$.
Sample 2
Input
4 1 1 1 1
Output
0
A challenge on a card with 1 written on it always succeeds.
In the case of a tie, kiri wins.
Sample 3
Input
5 3 4 5 9 11
Output
0.4818994264
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。