codeforces-scrape

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

1850E.md (2803B)


      1 Source: https://codeforces.com/problemset/problem/1850/E
      2 
      3 E. Cardboard for Pictures
      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 Mircea has $n$ pictures. The $i$-th picture is a square with a side length of $s_i$ centimeters.
     22 
     23 He mounted each picture on a square piece of cardboard so that each picture has a border of $w$ centimeters of cardboard on all sides. In total, he used $c$ square centimeters of cardboard. Given the picture sizes and the value $c$, can you find the value of $w$?
     24 
     25  ![](https://espresso.codeforces.com/ca3af639b1185e8c68ad3a1db4b4270c7a63bc44.png) A picture of the first test case. Here $c = 50 = 5^2 + 4^2 + 3^2$, so $w=1$ is the answer. 
     26 
     27 Please note that the piece of cardboard goes behind each picture, not just the border.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     32 
     33 The first line of each test case contains two positive integers $n$ ($1 \leq n \leq 2 \cdot 10^5$) and $c$ ($1 \leq c \leq 10^{18}$) — the number of paintings, and the amount of used square centimeters of cardboard.
     34 
     35 The second line of each test case contains $n$ space-separated integers $s_i$ ($1 \leq s_i \leq 10^4$) — the sizes of the paintings.
     36 
     37 The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     38 
     39 Additional constraint on the input: Such an integer $w$ exists for each test case.
     40 
     41 Please note, that some of the input for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
     42 
     43 Output
     44 
     45 For each test case, output a single integer — the value of $w$ ($w \geq 1$) which was used to use exactly $c$ squared centimeters of cardboard.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 10
     53 3 50
     54 3 2 1
     55 1 100
     56 6
     57 5 500
     58 2 2 2 2 2
     59 2 365
     60 3 4
     61 2 469077255466389
     62 10000 2023
     63 10 635472106413848880
     64 9181 4243 7777 1859 2017 4397 14 9390 2245 7225
     65 7 176345687772781240
     66 9202 9407 9229 6257 7743 5738 7966
     67 14 865563946464579627
     68 3654 5483 1657 7571 1639 9815 122 9468 3079 2666 5498 4540 7861 5384
     69 19 977162053008871403
     70 9169 9520 9209 9013 9300 9843 9933 9454 9960 9167 9964 9701 9251 9404 9462 9277 9661 9164 9161
     71 18 886531871815571953
     72 2609 10 5098 9591 949 8485 6385 4586 1064 5412 6564 8460 2245 6552 5089 8353 3803 3764
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 1
     79 2
     80 4
     81 5
     82 7654321
     83 126040443
     84 79356352
     85 124321725
     86 113385729
     87 110961227
     88 ```
     89 
     90 Note
     91 
     92 The first test case is explained in the statement.
     93 
     94 For the second test case, the chosen $w$ was $2$, thus the only cardboard covers an area of $c = (2 \cdot 2 + 6)^2 = 10^2 = 100$ squared centimeters.
     95 
     96 For the third test case, the chosen $w$ was $4$, which obtains the covered area $c = (2 \cdot 4 + 2)^2 \times 5 = 10^2 \times 5 = 100 \times 5 = 500$ squared centimeters.