No.66 Shine☆National Takoyaki Cup

問題提出提出一覧質問統計解説

問題一覧 > 通常問題

No.66 Shine☆National Takoyaki Cup

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が $10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : （AC するまで非表示） / 解いたユーザー数 148
作問者 :

なお

お気に入りにしたユーザー ProblemId : 93 / 自分の提出

問題文最終更新日: 2026-06-26 18:54:34

This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

yukicoder contest 52 (順位表) の他の問題:

Problem Statement

Taro is going to participate in the "Shine☆National Takoyaki Cup".

In this competition, a total of $2^M$ players take part,
and they compete in a tournament format, where each winner goes on to play against other players who have also advanced,
to determine the champion.

The $2^M$ players are assigned player numbers $N_1 ～ N_{2^M}$,
and Taro is assigned the number $N_1$.

Example for $M = 3$:

In round $1$ of the tournament, player $N_{2j-1}$ plays against player $N_{2j}$. $(1 \leq j \leq 2^{M-1})$
Then, denoting the winner of each of these matches by $N'_j $,
in the next round $2$, player $N'_{2k-1}$ plays against player $N'_{2k}$, and so on, $(1 \leq k \leq 2^{M-2})$
so that $1$ champion is determined after a total of $M$ rounds.

Each of the $2^M$ players has a strength parameter $S_i$.
When player $A$ and player $B$ play a match, with strength parameters $S_a, S_b$ respectively,
the probability that player $A$ wins is $P_a = {S_a}^2 / ({S_a}^2+{S_b}^2) $, and the probability that player $B$ wins is $P_b = {S_b}^2 / ({S_a}^2+{S_b}^2) $
.
Factors other than the above, such as compatibility between players, do not affect the outcome.

Given the strength parameters of the $2^M$ players as input,
find the probability that Taro wins the championship.

Input

\(M\)
\(S_1\)
\(S_2\)
\(\dots\)
\(S_i\)
\(\dots\)
\(S_{2^M}\)

Line $1$ contains $M\ (1 \leq M \leq 10)$, which represents the number of players $(2^M)$.
Each of the following $2^M$ lines contains $S_i\ (1 \leq S_i \leq 30000, 1 \leq i \leq 2^M)$, which represents the strength parameter of each player.

Output

Output the probability that Taro wins the championship as a decimal in the range from $0$ to $1$.
An error is tolerated if at least one of the absolute error or the relative error is at most $10^{−6}$.
Print a newline at the end.

Sample

Sample 1

Input

Output

0.0147294

In round $1$, Taro $N_1$ (strength $1$) plays against player $N_2$ (strength $2$).
The probability that Taro $N_1$ wins is $1^2 / (1^2+2^2) = 0.2$,
and the probability that player $N_2$ wins is $2^2 / (1^2+2^2) = 0.8$.
Similarly, player $N_3$ (strength $3$) plays against player $N_4$ (strength $4$),
where the probability that player $N_3$ wins is $3^2 / (3^2+4^2) = 0.36$,
and the probability that player $N_4$ wins is $4^2 / (3^2+4^2) = 0.64$.

Next, in round $2$, Taro plays against the winner of player $N_3$ and player $N_4$.
When Taro plays against player $N_3$, the probability that Taro wins is $1^2 / (1^2+3^2) = 0.1$,
and when Taro plays against player $N_4$, the probability that Taro wins is $1^2 / (1^2+4^2) = 0.0588235$,
so the probability that Taro wins round $2$ is $0.36 \times 0.1 + 0.64 \times 0.0588235 = 0.0736467$.
Multiplying this by $0.2$, the probability that Taro wins round $1$, gives $0.0147294$, which is the probability that Taro wins the championship.

Sample 2

Input

1
3000
2995

Output

0.5008340

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。