codeforces-scrape

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

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