/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
長さが A_1,\ldots,A_N の N 本の棒が袋に入っています。
あなたは次の操作を K 回繰り返します。
- 袋に入っている棒の中で最も長いものを 1 本取り出し、二等分して、2 本の棒を袋に戻す
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 番目のテストケースでは、最初、袋の中には長さが 20,30,40 の 3 本の棒が入っています。操作は次のように進行します。
- 長さ 40 の棒を袋から取り出し、長さ 20 の棒 2 本を袋に戻す。袋の中の棒の長さは 20,20,20,30 となる。
- 長さ 30 の棒を袋から取り出し、長さ 15 の棒 2 本を袋に戻す。袋の中の棒の長さは 15,15,20,20,20 となる。
- 長さ 20 の棒を袋から取り出し、長さ 10 の棒 2 本を袋に戻す。袋の中の棒の長さは 10,10,15,15,20,20 となる。
- 長さ 20 の棒を袋から取り出し、長さ 10 の棒 2 本を袋に戻す。袋の中の棒の長さは 10,10,10,10,15,15,20 となる。
操作後に長い方から 5 番目の棒の長さは 10 です。
Score : 475 points
Problem Statement
There are N sticks in a bag, with lengths A_1,\ldots,A_N.
You repeat the following operation K times.
- Take out any one of the longest sticks in the bag, split it into two equal halves, and put the two sticks back into the bag.
After K operations, among the N+K sticks in the bag, find the length of the X-th longest one.
You are given T test cases; answer each of them.
Constraints
- 1 \leq T \leq 10^5
- For each test case:
- 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
- The sum of N over all test cases does not exceed 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T
\mathrm{testcase}_i represents the i-th test case and is given in the following format:
N K X A_1 \ldots A_N
Output
Print T lines. In the i-th line (1 \leq i \leq T), output the answer for the i-th test case.
Your answer will be judged correct if the absolute or relative error is at most 10^{-9}.
Sample Input 1
2 3 4 5 40 20 30 10 100 50 1 2 3 4 5 6 7 8 9 10
Sample Output 1
10.00000000000000000000 0.50000000000000000000
In the 1-st test case, initially the bag contains 3 sticks of lengths 20,30,40. The operations proceed as follows.
- Take out the stick of length 40 from the bag, split it into two sticks of length 20, and put them back. The stick lengths in the bag become 20,20,20,30.
- Take out the stick of length 30 from the bag, split it into two sticks of length 15, and put them back. The stick lengths in the bag become 15,15,20,20,20.
- Take out a stick of length 20 from the bag, split it into two sticks of length 10, and put them back. The stick lengths in the bag become 10,10,15,15,20,20.
- Take out a stick of length 20 from the bag, split it into two sticks of length 10, and put them back. The stick lengths in the bag become 10,10,10,10,15,15,20.
After the operations, the 5-th longest stick has length 10.