/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
2N 個の壺があります。このうち i 個目の壺 (1 ≤ i ≤ 2N) の市場価格は p_i 円です。
これから、あなたとダックスフンドのルンルンは交互に壺を一つずつ取っていきます。あなたから始めて、すべての壺があなたかルンルンに取られるまで続けます。ルンルンは壺の市場価格がわからないので、毎回、残っている壺の中から無作為に等確率で一つを選びます。あなたはこのルンルンの行動と、壺の市場価格を知っています。
あなたの目的は、取る壺の市場価格の合計を S 円としたとき、S の期待値を最大化することです。最適な戦略を取ったときの S の期待値を求めてください。
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ p_i ≤ 2 × 10^5
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
p_1
:
p_{2N}
出力
S の期待値を最大化する戦略を取ったときの S の期待値を出力せよ。出力は、ジャッジの出力からの絶対誤差または相対誤差が 10^{-9} 以下であれば正答とみなされる。
入力例 1
1 150000 108
出力例 1
150000.0
当然、15 万円の壺を選ぶべきです。
入力例 2
2 50000 50000 100000 100000
出力例 2
183333.3333333333
あなたはまず、10 万円の壺のうち一つを取ります。もう一つの 10 万円の壺は、次のルンルンの番で取られなければ手に入り、その確率は 2/3 です。もしその壺を取られてしまった場合は、5 万円の壺で我慢することになります。以上から、最適な戦略を取ったときの S の期待値は 2/3 × (100000 + 100000) + 1/3 × (100000 + 50000) = 183333.3333… となります。
Score : 100 points
Problem Statement
We have 2N pots. The market price of the i-th pot (1 ≤ i ≤ 2N) is p_i yen (the currency of Japan).
Now, you and Lunlun the dachshund will alternately take one pot. You will go first, and we will continue until all the pots are taken by you or Lunlun. Since Lunlun does not know the market prices of the pots, she will always choose a pot randomly from the remaining pots with equal probability. You know this behavior of Lunlun, and the market prices of the pots.
Let the sum of the market prices of the pots you take be S yen. Your objective is to maximize the expected value of S. Find the expected value of S when the optimal strategy is adopted.
Constraints
- 1 ≤ N ≤ 10^5
- 1 ≤ p_i ≤ 2 × 10^5
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N
p_1
:
p_{2N}
Output
Print the expected value of S when the strategy to maximize the expected value of S is adopted. The output is considered correct if its absolute or relative error from the judge's output is at most 10^{-9}.
Sample Input 1
1 150000 108
Sample Output 1
150000.0
Naturally, you should choose the 150000 yen pot.
Sample Input 2
2 50000 50000 100000 100000
Sample Output 2
183333.3333333333
First, you will take one of the 100000 yen pots. The other 100000 yen pot will become yours if it is not taken in Lunlun's next turn, with probability 2/3. If it is taken, you will have to settle for a 50000 yen pot. Thus, the expected value of S when the optimal strategy is adopted is 2/3 × (100000 + 100000) + 1/3 × (100000 + 50000) = 183333.3333…