← 返回题目列表

AtCoder · abc424_e

H. 切成两半

中文机器翻译题面 查看原题

分数: 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.