codeforces-scrape

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

1873E.md (2441B)


      1 Source: https://codeforces.com/problemset/problem/1873/E
      2 
      3 E. Building an Aquarium
      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 love fish, that's why you have decided to build an aquarium. You have a piece of coral made of $n$ columns, the $i$-th of which is $a_i$ units tall. Afterwards, you will build a tank around the coral as follows:
     22 
     23 * Pick an integer $h \geq 1$ — the height of the tank. Build walls of height $h$ on either side of the tank.
     24 * Then, fill the tank up with water so that the height of each column is $h$, unless the coral is taller than $h$; then no water should be added to this column.
     25 
     26 For example, with $a=[3,1,2,4,6,2,5]$ and a height of $h=4$, you will end up using a total of $w=8$ units of water, as shown.  ![](https://espresso.codeforces.com/09066a721673d03ce81c6cbf6841aabc5a329206.png)  You can use at most $x$ units of water to fill up the tank, but you want to build the biggest tank possible. What is the largest value of $h$ you can select?
     27 
     28 Input
     29 
     30 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     31 
     32 The first line of each test case contains two positive integers $n$ and $x$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq x \leq 10^9$) — the number of columns of the coral and the maximum amount of water you can use.
     33 
     34 The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^9$) — the heights of the coral.
     35 
     36 The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     37 
     38 Output
     39 
     40 For each test case, output a single positive integer $h$ ($h \geq 1$) — the maximum height the tank can have, so you need at most $x$ units of water to fill up the tank.
     41 
     42 We have a proof that under these constraints, such a value of $h$ always exists.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 7 9
     52 
     53 3 1 2 4 6 2 5
     54 
     55 3 10
     56 
     57 1 1 1
     58 
     59 4 1
     60 
     61 1 4 3 4
     62 
     63 6 1984
     64 
     65 2 6 5 9 1 8
     66 
     67 1 1000000000
     68 
     69 1
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 4
     76 4
     77 2
     78 335
     79 1000000001
     80 ```
     81 
     82 Note
     83 
     84 The first test case is pictured in the statement. With $h=4$ we need $8$ units of water, but if $h$ is increased to $5$ we need $13$ units of water, which is more than $x=9$. So $h=4$ is optimal.
     85 
     86 In the second test case, we can pick $h=4$ and add $3$ units to each column, using a total of $9$ units of water. It can be shown that this is optimal.
     87 
     88 In the third test case, we can pick $h=2$ and use all of our water, so it is optimal.