codeforces-scrape

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

1993C.md (2727B)


      1 Source: https://codeforces.com/problemset/problem/1993/C
      2 
      3 C. Light Switches
      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 There is an apartment consisting of $n$ rooms, each with its light initially turned off.
     22 
     23 To control the lights in these rooms, the owner of the apartment decided to install chips in the rooms so that each room has exactly one chip, and the chips are installed at different times. Specifically, these times are represented by the array $a_1, a_2, \ldots, a_n$, where $a_i$ is the time (in minutes) at which a chip is installed in the $i$-th room.
     24 
     25 As soon as a chip is installed, it changes the room's light status every $k$ minutes — it turns on the light for $k$ minutes, then turns it off for the next $k$ minutes, then turns it back on for the next $k$ minutes, and so on. In other words, the light status is changed by the chip at minute $a_i$, $a_i + k$, $a_i + 2k$, $a_i + 3k$, $\ldots$ for the $i$-th room.
     26 
     27 What is the earliest moment when all rooms in the apartment have their lights turned on?
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of rooms in the apartment and the period of the chips.
     34 
     35 The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the moments when the chips are installed.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the answer to the question (in minutes). If there is no such moment that the lights are turned on in all the rooms, print $-1$ instead.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 9
     49 
     50 4 4
     51 
     52 2 3 4 5
     53 
     54 4 3
     55 
     56 2 3 4 5
     57 
     58 4 3
     59 
     60 3 4 8 9
     61 
     62 3 3
     63 
     64 6 2 1
     65 
     66 1 1
     67 
     68 1
     69 
     70 7 5
     71 
     72 14 34 6 25 46 7 17
     73 
     74 6 5
     75 
     76 40 80 99 60 90 50
     77 
     78 6 5
     79 
     80 64 40 50 68 70 10
     81 
     82 2 1
     83 
     84 1 1000000000
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 5
     91 -1
     92 10
     93 8
     94 1
     95 47
     96 100
     97 -1
     98 -1
     99 ```
    100 
    101 Note
    102 
    103 In the first test case, all lights will be on by the minute $5$ without any of them being turned off by the chips. The answer is $5$.
    104 
    105 In the second test case, due to $k=3$, the $1$-st light will be on at minutes $2, 3, 4, 8, 9, 10, 14, \ldots$; meanwhile, the $4$-th light will be on at minutes $5, 6, 7, 11, 12, 13, 17, \ldots$. These two sequences don't have any number in common, so they will never be on at the same time.
    106 
    107 In the third test case, it can be seen that the $1$-st and $2$-nd lights will be turned off at minutes $6$ and $7$, but the chips will turn them back on at minutes $9$ and $10$. The $3$-rd and $4$-th lights will also be on at minute $10$, so the answer is $10$.