/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
すぬけくんは明日の運勢を占いました． その結果，N 個のシナリオのうちどれか一つが等確率で発生し，そのうち i 番目のシナリオでは A_i 円を失うことを知りました．
そこですぬけくんは，今日保険に入ることにしました． 保険会社に x 円を支払ったとすると，A_i 円を失った場合には \min(A_i,2x) 円が補填されます． ここで，x として任意の非負実数を選ぶことができます．
すぬけくんは，最終的に自分が失う金額（=x+A_i-\min(A_i,2x)）の期待値を最小化したいです． この最小値を求めてください．
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
答えを出力せよ． 絶対誤差または相対誤差が 10^{-6} 以下ならば，正解と判定される．
入力例 1
3 3 1 4
出力例 1
1.83333333333333333333
x=1.5 とするのが最適です． 1.5 円支払ったあと，以下の 3 つのシナリオが等確率で起こります．
-
シナリオ 1: 3 円失ったあと，\min(3,2x)=3 円が補填される． 最終的にすぬけくんが失う金額は，x+A_1-\min(A_1,2x)=1.5+3-3=1.5 円である．
-
シナリオ 2: 1 円失ったあと，\min(1,2x)=1 円が補填される． 最終的にすぬけくんが失う金額は，x+A_2-\min(A_2,2x)=1.5+1-1=1.5 円である．
-
シナリオ 3: 4 円失ったあと，\min(4,2x)=3 円が補填される． 最終的にすぬけくんが失う金額は，x+A_3-\min(A_3,2x)=1.5+4-3=2.5 円である．
よって，失う金額の期待値は，(1.5+1.5+2.5)/3=1.833333\cdots です．
入力例 2
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
出力例 2
362925658.10000000000000000000
Score : 500 points
Problem Statement
Snuke has read his own fortune for tomorrow, and learned that there are N scenarios that can happen, one of which will happen tomorrow with equal probability. The i-th scenario will cost him A_i yen (Japanese currency).
Following this, Snuke has decided to get insurance today. If he pays x yen to his insurance company, he will get compensation of \min(A_i,2x) yen when A_i yen is lost. Here, he can choose any non-negative real number as x.
Snuke wants to minimize the expected value of the amount of money he loses, which is x+A_i-\min(A_i,2x). Find the minimized value.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer. Your answer will be judged correct when its absolute or relative error is at most 10^{-6}.
Sample Input 1
3 3 1 4
Sample Output 1
1.83333333333333333333
The optimum choice is x=1.5. After paying 1.5 yen, one of the following three scenarios will happen with equal probability:
-
Scenario 1: Lose 3 yen and get compensation of \min(3,2x)=3 yen. After all, Snuke loses x+A_1-\min(A_1,2x)=1.5+3-3=1.5 yen.
-
Scenario 2: Lose 1 yen and get compensation of \min(1,2x)=1 yen. After all, Snuke loses x+A_2-\min(A_2,2x)=1.5+1-1=1.5 yen.
-
Scenario 3: Lose 4 yen and get compensation of \min(4,2x)=3 yen. After all, Snuke loses x+A_3-\min(A_3,2x)=1.5+4-3=2.5 yen.
Thus, the expected amount of money lost is (1.5+1.5+2.5)/3=1.833333\cdots yen.
Sample Input 2
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
Sample Output 2
362925658.10000000000000000000