分数: 475 点
问题陈述
有 N 装在袋子里,有长度 A_1,\ldots,A_N.
您重复以下操作 K 次。
- 取出袋子中最长的一根棍子,将其分成相等的两半,然后将两根棍子放回袋子中。
之后 K 操作,其中 N+K 粘在袋子里,求长度 X- 第最长的一个。
你被给予 T 测试用例;回答他们每个人。
约束
- 1 \leq T \leq 10^5
- 对于每个测试用例:
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq K \leq 10^9
- 1 \leq X \leq N+K
- 总和 N 所有测试用例不超过 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T
\mathrm{testcase}_i 代表 i-第一个测试用例,以以下格式给出:
N K X A_1 \ldots A_N
输出
打印 T 行。 在 i第行 (1 \leq i \leq T),输出答案 i- 第一个测试用例。
如果绝对或相对误差最多为,则您的答案将被判断为正确 10^{-9}.
示例输入 1
2 3 4 5 40 20 30 10 100 50 1 2 3 4 5 6 7 8 9 10
示例输出 1
10.00000000000000000000 0.50000000000000000000
在 1-st 测试用例,最初包中包含 3 长度棒 20,30,40。操作进行如下。
- 取出长度的棍子 从袋子里取出 40 ,将其分成两根长度相同的棒 20,然后把它们放回去。袋子里的棍子长度变成 20,20,20,30.
- 取出长度的棍子 从袋子里取出 30 ,将其分成两根长度相同的棒 15,然后把它们放回去。袋子里的棍子长度变成 15,15,20,20,20.
- 拿出一根长度的棍子 20 ,将其分成两根长度相同的棒 10,然后把它们放回去。袋子里的棍子长度变成 10,10,15,15,20,20.
- 拿出一根长度的棍子 20 ,将其分成两根长度相同的棒 10,然后把它们放回去。袋子里的棍子长度变成 10,10,10,10,15,15,20.
操作后, 5- 第最长的棍子有长度 10.