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$.