codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1175C.md (1572B)


      1 Source: https://codeforces.com/problemset/problem/1175/C
      2 
      3 C. Electrification
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 At first, there was a legend related to the name of the problem, but now it's just a formal statement.
     22 
     23 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.
     24 
     25 The function $f_k(x)$ can be described in the following way:
     26 
     27 * form a list of distances $d_1, d_2, \dots, d_n$ where $d_i = |a_i - x|$ (distance between $a_i$ and $x$);
     28 * sort list $d$ in non-descending order;
     29 * take $d_{k + 1}$ as a result.
     30 
     31 If there are multiple optimal answers you can print any of them.
     32 
     33 Input
     34 
     35 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.
     36 
     37 The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \lt n$) — the number of points and constant $k$.
     38 
     39 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$) — points in ascending order.
     40 
     41 It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 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.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 3 2
     54 1 2 5
     55 2 1
     56 1 1000000000
     57 1 0
     58 4
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 3
     65 500000000
     66 4
     67 ```