配点 : $100$ 点

問題文

$2N$ 個の壺があります。このうち $i$ 個目の壺 $(1 \leq i \leq 2N)$ の市場価格は $p_i$ 円です。

これから、あなたとダックスフンドのルンルンは交互に壺を一つずつ取っていきます。あなたから始めて、すべての壺があなたかルンルンに取られるまで続けます。ルンルンは壺の市場価格がわからないので、毎回、残っている壺の中から無作為に等確率で一つを選びます。あなたはこのルンルンの行動と、壺の市場価格を知っています。

あなたの目的は、取る壺の市場価格の合計を $S$ 円としたとき、$S$ の期待値を最大化することです。最適な戦略を取ったときの $S$ の期待値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq p_i \leq 2 \times 10^5$
• 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$p_1$

$:$

$p_{2N}$

出力

$S$ の期待値を最大化する戦略を取ったときの $S$ の期待値を出力せよ。出力は、ジャッジの出力からの絶対誤差または相対誤差が $10^{-9}$ 以下であれば正答とみなされる。

1
150000
108

150000.0

当然、$15$ 万円の壺を選ぶべきです。

2
50000
50000
100000
100000

183333.3333333333

あなたはまず、$10$ 万円の壺のうち一つを取ります。もう一つの $10$ 万円の壺は、次のルンルンの番で取られなければ手に入り、その確率は $2/3$ です。もしその壺を取られてしまった場合は、$5$ 万円の壺で我慢することになります。以上から、最適な戦略を取ったときの $S$ の期待値は $2/3 \times (100000 + 100000) + 1/3 \times (100000 + 50000) = 183333.3333 \cdots$ となります。