2207B.md (3787B)
1 Source: https://codeforces.com/problemset/problem/2207/B 2 3 B. One Night At Freddy's 4 5 time limit per test 6 7 1 second 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 | | 22 | --- | 23 | [Five Nights at Freddy's 1 Song — The Living Tombstone](https://www.youtube.com/watch?v=l18A5BOTlzE&t=6s) | 24 25 Let $n, m, \ell$ be positive integers. You have made the unfortunate decision to work as a night guard at Freddy Fazbear's Pizzeria, where there are $m$ animatronics numbered $1, \ldots, m$ waiting to jumpscare you. 26 27 The night consists of $\ell$ seconds, numbered $1, \ldots, \ell$. The $j$-th of the $m$ animatronics has a danger level $d_j$, and initially $d_1 = \ldots = d_m = 0$. Every second, the danger level of exactly one animatronic will increase by $1$, and throughout the night, you are able to observe all values of $d_j$ at the current time. For example, if $m = 2$, one possible list of danger levels after $5$ seconds is $[d_1, d_2] = [2, 3]$. 28 29 You are not defenseless, however. At each of the $n$ fixed times $a_i$ ($1 \leq a_1 \lt \ldots \lt a_n \leq \ell$), you can shine your flashlight on exactly one animatronic $j_i$ of your choice. This occurs immediately after the $a_i$-th second and sets its danger level back to zero, i.e. $d_{j_i} := 0$. Note that this choice is made independently for each flashlight use $a_i$. Continuing the example from before, if $a_1 = 5$ and you choose to flash the second animatronic at that time, the danger levels after $5$ seconds will be $[d_1, d_2] = [2, 0]$. 30 31 Let the overall danger be the maximum danger across all animatronics, i.e. $\max_{1 \leq j \leq m} d_j$. You will lose if the overall danger at the end of the night (after $\ell$ seconds) is greater than $x$. Find the minimum value of $x$ such that regardless of the actions of the animatronics, you can guarantee that overall danger will be less than or equal $x$. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The first line of each test case contains three integers $n$, $m$, and $\ell$ ($1 \leq n, m, \ell \leq 2 \cdot 10^5, n \leq \ell, 1 \leq m \cdot \ell \leq 2 \cdot 10^5$) — the number of flashlight actions, animatronics, and the length of the night, respectively. 38 39 The next line contains $n$ integers $a_i$ ($1 \leq a_1 \lt \ldots \lt a_n \leq \ell$) — the times at which you get to shine your flashlight. 40 41 It is guaranteed that the sum of $m \cdot \ell$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each test case, output a single integer — the minimum $x$ such that you can guarantee that your final danger level is at most $x$. 46 47 Example 48 49 Input 50 51 ``` 52 7 53 54 1 2 10 55 56 10 57 58 5 1 32 59 60 1 4 9 16 25 61 62 2 3 40 63 64 13 37 65 66 2 2 7 67 68 6 7 69 70 8 5 60 71 72 3 17 20 28 36 44 45 50 73 74 6 7 1987 75 76 6 7 66 77 666 777 77 78 1 1 1 79 80 1 81 ``` 82 83 Output 84 85 ``` 86 5 87 88 7 89 90 19 91 92 1 93 94 19 95 96 1477 97 98 0 99 ``` 100 101 Note 102 103 In the first test case, there are $2$ animatronics and a night length of $10$, and you get to flash after the $10$-th second. We will show that $x = 5$ is always possible. After $10$ seconds, notice that one animatronic must have at least $5$ danger, and the other must have at most $5$ danger. So, we can flash the higher one and get a final danger level at most $5$. It can be shown that $5$ is the minimum possible value of $x$. 104 105 In the second test case, there is only one animatronic and a night length of $32$. Notice that in this case, the animatronic just increments its danger by $1$ each second. So, after the $25$-th second, we reset its danger to $0$. Seven more seconds pass before the night ends, so the final danger we get is always $7$. 106 107 In the third test case, it can be proven that the minimum possible value of $x$ is $19$.