codeforces-scrape

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

1987C.md (1721B)


      1 Source: https://codeforces.com/problemset/problem/1987/C
      2 
      3 C. Basil's Garden
      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 are $n$ flowers in a row, the $i$-th of them initially has a positive height of $h_i$ meters.
     22 
     23 Every second, the wind will blow from the left, causing the height of some flowers to decrease.
     24 
     25 Specifically, every second, for each $i$ from $1$ to $n$, in this order, the following happens:
     26 
     27 * If $i = n$ or $h_i \gt h_{i + 1}$, the value of $h_i$ changes to $\max(0, h_i - 1)$.
     28 
     29 How many seconds will pass before $h_i=0$ for all $1 \le i \le n$ for the first time?
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of flowers.
     36 
     37 The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10 ^ 9$) — the heights of the flowers.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the number of seconds that will pass before $h_i=0$ for all $1 \le i \le n$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 3
     53 
     54 1 1 2
     55 
     56 2
     57 
     58 3 1
     59 
     60 1
     61 
     62 9
     63 
     64 5
     65 
     66 7 4 4 3 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 4
     73 3
     74 9
     75 7
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, the flower heights change as follows: $[1, 1, 2] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$.
     81 
     82 In the second test case, the flower heights change as follows: $[3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [0, 0]$.