codeforces-scrape

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

2167E.md (3055B)


      1 Source: https://codeforces.com/problemset/problem/2167/E
      2 
      3 E. khba Loves to Sleep!
      4 
      5 time limit per test
      6 
      7 3 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 khba has $n$ friends, each standing on a line at position $a_i$, and each of them is in the range $[0, x]$.
     22 
     23 They all want to come to him. One of his friends, Isamatdin, gave him $k$ teleports. Each friend will walk to the nearest teleport (choosing the shortest distance). Once a friend reaches a teleport, khba and the friend can instantly meet.
     24 
     25 But khba is so tired that he'll be sleeping while his friends are walking toward him. Now he wants to choose $k$ teleport positions so that their positions are distinct and lie within the range $[0, x]$, in order to maximize the time it takes for the first friend who reaches a teleport to reach it. Assume that friends move at the same speed.
     26 
     27 Since khba isn't good at calculations, you should output the $k$ chosen teleport positions.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.
     32 
     33 The first line of each test case contains three integers $n$, $k$, and $x$ ($1 \leq n, k \leq 2 \cdot 10^5$, $k - 1 \leq x \leq 10^9$) — the number of friends, the number of teleports, and the range of possible positions for the teleports.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq x$) — the positions of khba's friends.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 It is guaranteed that the sum of $k$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single line containing $k$ integers — the $k$ chosen teleport positions. The positions must be distinct and lie within the range $[0, x]$. The positions may be output in any order.
     44 
     45 If there are multiple optimal choices, output any of them.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 10
     53 
     54 4 1 4
     55 
     56 1 0 2 4
     57 
     58 5 5 4
     59 
     60 0 1 2 3 4
     61 
     62 2 1 4
     63 
     64 4 0
     65 
     66 3 4 6
     67 
     68 2 4 3
     69 
     70 3 2 12
     71 
     72 6 12 0
     73 
     74 4 3 12
     75 
     76 8 12 0 4
     77 
     78 1 1 1000000000
     79 
     80 0
     81 
     82 1 1 1000000000
     83 
     84 1000000000
     85 
     86 3 4 9
     87 
     88 8 7 9
     89 
     90 3 4 9
     91 
     92 2 0 1
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 3 
     99 0 1 2 3 4 
    100 2 
    101 0 1 5 6 
    102 3 9 
    103 2 6 10 
    104 1000000000 
    105 0 
    106 0 1 2 3 
    107 6 7 8 9
    108 ```
    109 
    110 Note
    111 
    112 Sample 1. Friends at positions $[1,0,2,4]$. Chosen teleport position: $[3]$.
    113 
    114 Nearest teleport for each friend is in $3$, minimal times for friends are $[2, 3, 1, 1]$, respectively.
    115 
    116 Sample 2. Friends at positions $[0,1,2,3,4]$. Chosen teleport positions: $[0,1,2,3,4]$.
    117 
    118 Minimal times for friends are $[0, 0, 0, 0, 0]$, respectively.
    119 
    120 Sample 3. Friends at positions $[4,0]$. Chosen teleport position: $[2]$.
    121 
    122 Minimal times for friends are $[2, 2]$, respectively.
    123 
    124 Sample 4. Friends at positions $[2,4,3]$. Chosen teleport positions: $[0,1,5,6]$.
    125 
    126 Minimal times for friends are $[1, 1, 2]$, respectively.
    127 
    128 Sample 5. Friends at positions $[6,12,0]$. Chosen teleport positions: $[3,9]$.
    129 
    130 Minimal times for friends are $[3, 3, 3]$, respectively.