问题陈述
高桥要更新了 N 应用编号的应用 1,应用程序 2, \ldots和应用程序 N.
正在更新应用程序 i (1\leq i\leq N) 成本 T_i 时间单位。
Takahashi 可以选择要更新的应用程序的顺序。
开始时间 0,他的电脑按照指定的顺序一一更新应用程序。
正式来说,如果他让 i-th (1\leq i\leq N)要更新的应用程序是应用程序 p_i,计算机的行为如下:
- 更新应用 p_k 从时间 (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}).
他希望选择顺序,以便在检查更新进度时,可以尽可能正确地估计整个更新所需的总持续时间。
但是,在更新期间,他只能访问单个整数 k,这表明 k第次更新正在进行中。
如果他认识到 k- 第次更新正在进行中 t,他估计整个更新的持续时间是 f(t)=\frac{N}{k-0.5}\cdot t.
在此,当 i-th 更新开始,他认识到 i第次更新正在进行中。
具体来说,在某个时间 0 他认为 1-st 更新正在进行中;
当 i-th 更新完成并且 (i+1)第次更新开始,他认为 (i+1)-第更新是
正在进行中。
让 S\left(=\displaystyle\sum_{i=1}^N T_i\right) 是整个更新的总持续时间。 假设他估计整个更新的持续时间 t,这是一个随机实变量,选自 0 (含)至 t (独家)均匀随机。 找到最小期望值 \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,他的预计持续时间
如果他及时检查进度,则 f(t) 整个更新 t (0\leq t<10)是:
- 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.
当 t 从范围中选择 0\leq t\lt 10 均匀随机,期望值 \lvert f(t)-S\rvert is \frac{46}{15}=3.066\cdots, 这是可能的最小值。
示例输入 2
3 3 1 1
示例输出 2
1.420000000000000
的预期值 \lvert f(t)-S\rvert 为最小值 如果他指定应用程序的更新顺序是 1\to 3\to 2.