Electrification
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
At first, there was a legend related to the name of the problem, but now it's just a formal statement.
You are given $n$ points $a_1, a_2, \dots, a_n$ on the $OX$ axis. Now you are asked to find such an integer point $x$ on $OX$ axis that $f_k(x)$ is minimal possible.
The function $f_k(x)$ can be described in the following way:
- form a list of distances $d_1, d_2, \dots, d_n$ where $d_i = |a_i - x|$ (distance between $a_i$ and $x$);
- sort list $d$ in non-descending order;
- take $d_{k + 1}$ as a result.
If there are multiple optimal answers you can print any of them.
The first line contains single integer $T$ ($ 1 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent.
The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k < n$) — the number of points and constant $k$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^9$) — points in ascending order.
It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.
Print $T$ integers — corresponding points $x$ which have minimal possible value of $f_k(x)$. If there are multiple answers you can print any of them.
Input
The first line contains single integer $T$ ($ 1 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent.
The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k < n$) — the number of points and constant $k$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^9$) — points in ascending order.
It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.
Output
Print $T$ integers — corresponding points $x$ which have minimal possible value of $f_k(x)$. If there are multiple answers you can print any of them.
3
3 2
1 2 5
2 1
1 1000000000
1 0
4
3
500000000
4
20240326集训
- Status
- Done
- Rule
- IOI
- Problem
- 7
- Start at
- 2024-3-26 19:00
- End at
- 2024-3-26 21:00
- Duration
- 2 hour(s)
- Host
-
SamuelXuch
- Partic.
- 14