#P18376. Ethanol

Ethanol

Ethanol

题目描述

小青鱼正在摆弄一些瓶子。桌上有 n+2n+2 个足够大的容器,编号为 0,1,…,n+10,1,\ldots,n+1。

最初,容器 00 中装有质量为 X/1000X/1000 的水,容器 n+1n+1 为空。对于每个 i=1,2,…,ni=1,2,\ldots,n,容器 ii 中装有总质量为 11 的均匀混合液,其中乙醇的质量为 Ei/1000E_i/1000,水的质量为 1−Ei/10001-E_i/1000。

小青鱼可以执行任意有限次下述操作,也可以一次都不执行:

  1. 选择一个下标 ii(0≤i≤n0\le i\le n)和一个实数 x>0x>0。若 i≥1i\ge1,要求容器 ii 此时装有的混合液质量至少为 1+x1+x;对于 i=0i=0,不要求满足这个条件。
  2. 从容器 ii 向容器 i+1i+1 转移质量为 xx 的液体,然后搅拌容器 i+1i+1 中的液体,使其混合均匀。

请你求出:经过有限次操作后,最终可能进入容器 n+1n+1 的乙醇质量的上确界,即最小的上界。这个值不一定能通过某个有限的操作序列恰好取到。

输入格式

输入包含多组测试数据。第一行包含一个整数 TT(1≤T≤10001\le T\le1000),表示测试数据组数。

对于每组测试数据:

第一行包含两个整数 n,Xn,X,满足 1≤n≤201\le n\le20,1≤X≤10001\le X\le1000。

第二行包含 nn 个整数 E1,E2,…,EnE_1,E_2,\ldots,E_n,满足 0≤Ei≤10000\le E_i\le1000。

输出格式

对于每组测试数据,输出一行,包含一个实数,表示操作后容器 n+1n+1 中乙醇质量的上确界。

你的答案的绝对误差或相对误差不超过 10−910^{-9} 即可。严格地说,设你的输出为 xx,评测答案为 yy,当且仅当

∣x−y∣≤10−9max⁡(1,∣y∣)|x-y|\le10^{-9}\max(1,|y|)

时,该答案被接受。

样例 1 输入

2
1 900
1000
2 345
678 910

样例 1 输出

0.59343034025940088812
0.29768625581348055032

样例 2 输入

1
3 210
406 364 961

样例 2 输出

0.18956125995075295122

样例说明

以样例 1 的第一组测试数据为例,可以通过下列操作,使最终进入容器 22 的乙醇质量等于 23/4523/45:

  1. 从容器 00 向容器 11 转移质量为 0.50.5 的水。
  2. 从容器 11 向容器 22 转移质量为 0.40.4 的混合液。
  3. 从容器 00 向容器 11 转移质量为 0.40.4 的水。
  4. 从容器 11 向容器 22 转移质量为 0.50.5 的混合液。

通过适当安排操作,实际上可以使转移到容器 22 的乙醇质量任意接近 0.593…0.593\ldots。