codeforces-scrape

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

1856C.md (1985B)


      1 Source: https://codeforces.com/problemset/problem/1856/C
      2 
      3 C. To Become Max
      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 You are given an array of integers $a$ of length $n$.
     22 
     23 In one operation you:
     24 
     25 * Choose an index $i$ such that $1 \le i \le n - 1$ and $a_i \le a_{i + 1}$.
     26 * Increase $a_i$ by $1$.
     27 
     28 Find the maximum possible value of $\max(a_1, a_2, \ldots a_n)$ that you can get after performing this operation at most $k$ times.
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of the test cases follows.
     33 
     34 The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 1000$, $1 \le k \le 10^{8}$) — the length of the array $a$ and the maximum number of operations that can be performed.
     35 
     36 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{8}$) — the elements of the array $a$.
     37 
     38 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     39 
     40 Output
     41 
     42 For each test case output a single integer — the maximum possible maximum of the array after performing at most $k$ operations.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 6
     50 
     51 3 4
     52 
     53 1 3 3
     54 
     55 5 6
     56 
     57 1 3 4 5 1
     58 
     59 4 13
     60 
     61 1 1 3 179
     62 
     63 5 3
     64 
     65 4 3 2 2 2
     66 
     67 5 6
     68 
     69 6 5 4 1 5
     70 
     71 2 17
     72 
     73 3 5
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 4
     80 7
     81 179
     82 5
     83 7
     84 6
     85 ```
     86 
     87 Note
     88 
     89 In the first test case, one possible optimal sequence of operations is: $[\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]$.
     90 
     91 In the second test case, one possible optimal sequence of operations is: $[1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$.