/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
高橋君はソフトウェア 1、ソフトウェア 2、\cdots、ソフトウェア N と番号づけられた N 個のソフトウェアのアップデートを行おうとしており、
ソフトウェア i (1\leq i\leq N) のアップデートには T_i だけ時間がかかります。
高橋君はこれらのアップデートを行う順番を指定する事ができ、
コンピュータは時刻 0 にアップデートを始め、 与えられた順番に従って 1 つずつアップデートを実行していきます。
すなわち、高橋君が i (1\leq i\leq N) 番目にソフトウェア p_i のアップデートを実行するように指定した時、コンピュータは次のように動きます。
- 時刻 (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}) から時刻 (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k}) までソフトウェア p_k のアップデートを行う。
高橋君はアップデートの実行中に状態を確認した時、 N 個のアップデート全体にかかる時間をなるべく正しく推定する事ができるように順番を定めたいと考えました。
ここで、アップデートの実行中は現在何番目のアップデートを実行しているかしか知ることができないため、
高橋君は時刻 t に k 番目のアップデートが行われていた時、アップデート全体にかかる時間を f(t)=\frac{N}{k-0.5}\cdot t と見積ります。
なお、i 番目のアップデートが始まるちょうどその時刻には i 番目のアップデートを実行しているとみなされます。
すなわち、時刻 0 には 1 番目のアップデートが実行されているとみなされ、
ちょうど i 番目のアップデートが終了し i+1 番目のアップデートが開始する時刻には i+1 番目のアップデートが実行されている
とみなされます。
アップデート全体にかかる時間を S\left(=\displaystyle\sum_{i=1}^N T_i\right) とし、 高橋君がアップデート全体にかかる時間を見積もる時刻 t が 0 以上 S 未満の実数から連続一様分布に従って選ばれる時、 \lvert f(t)-S\rvert の期待値が最小となるように高橋君が順番を指定した時の \lvert f(t)-S\rvert の期待値を求めてください。
制約
- 2\leq N\leq 18
- 1\leq T_i\leq 10^6
- 入力は整数
入力
入力は以下の形式で標準入力から与えられる。
N T_1 T_2 \ldots T_N
出力
高橋君が問題文のように順番を指定した時の \lvert f(t)-S\rvert の期待値を出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。
入力例 1
2 3 7
出力例 1
3.066666666666667
アップデートにかかる時間は S=3+7=10 となります。
高橋君がアップデートの順番をソフトウェア 1\to 2 と指定した時、時刻 t (0\leq t<10) に状態を確認した時のアップデート全体にかかる推定時間 f(t) は、
- 0\leq t< 3 において、f(t)=\frac{2}{1-0.5}\cdot t=4t,
- 3\leq t< 10 において、f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t
となります。t が 0\leq t\lt 10 の範囲から一様な確率で選ばれる時、\lvert f(t)-S\rvert の期待値は \frac{46}{15}=3.066\cdots となり、 この時が最小となります。
入力例 2
3 3 1 1
出力例 2
1.420000000000000
高橋君がアップデートの順番をソフトウェア 1\to 3\to 2 と指定した時、 \lvert f(t)-S\rvert の期待値は最小となります。
Problem Statement
Takahashi is going to update N apps numbered app 1, app 2, \ldots, and app N.
Updating app i (1\leq i\leq N) costs T_i units of time.
Takahashi can choose the order of the apps to update.
Starting at time 0, his computer updates the apps one by one in the specified order.
Formally, if he lets the i-th (1\leq i\leq N) app to be updated be app p_i, the computer behaves as follows:
- updates app p_k from time (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}) to time (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k}).
He wants to choose the order so that, when he checks the progress during the updates, he can estimate the total duration required for the entire updates as correctly as possible.
However, during the updates, he only has access to a single integer k, which indicates that the k-th update is underway.
If he recognizes that the k-th update is underway at time t, he estimates that the duration of the entire updates is f(t)=\frac{N}{k-0.5}\cdot t.
Here, at the time when the i-th update starts, he recognizes that the i-th update is underway.
Specifically, at time 0 he regards that the 1-st update is underway;
at the time when the i-th update finishes and (i+1)-th update starts, he regards that the (i+1)-th update is
underway.
Let S\left(=\displaystyle\sum_{i=1}^N T_i\right) be the total duration for the entire updates. Suppose he estimates the duration of the entire updates at time t, which is a random real variable chosen from 0 (inclusive) to t (exclusive) uniformly at random. Find the minimum expected value of \lvert f(t)-S\rvert when he chooses the permutation to minimize it.
Constraints
- 2\leq N\leq 18
- 1\leq T_i\leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N T_1 T_2 \ldots T_N
Output
Print the expected value of \lvert f(t)-S\rvert when he chooses the permutation to minimize it.
Your answer is considered correct if the absolute or relative error from the true value is at most 10^{-6}.
Sample Input 1
2 3 7
Sample Output 1
3.066666666666667
The total duration of the entire updates is S=3+7=10.
When he specify the updating order of the apps to be 1\to 2, his estimated duration f(t) of the entire updates if he checks the progress at time t (0\leq t<10) is:
- f(t)=\frac{2}{1-0.5}\cdot t=4t if 0\leq t< 3;
- f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t if 3\leq t< 10.
When t is chosen from the range 0\leq t\lt 10 uniformly at random, the expected value of \lvert f(t)-S\rvert is \frac{46}{15}=3.066\cdots, which is the minimum possible value.
Sample Input 2
3 3 1 1
Sample Output 2
1.420000000000000
The expected value of \lvert f(t)-S\rvert is minimum if he specifies the updating order of the apps to be 1\to 3\to 2.