codeforces-scrape

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

1111B.md (2049B)


      1 Source: https://codeforces.com/problemset/problem/1111/B
      2 
      3 B. Average Superhero Gang Power
      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 Every superhero has been given a power value by the Felicity Committee. The avengers crew wants to maximize the average power of the superheroes in their team by performing certain operations.
     22 
     23 Initially, there are $n$ superheroes in avengers team having powers $a_1, a_2, \ldots, a_n$, respectively. In one operation, they can remove one superhero from their team (if there are at least two) or they can increase the power of a superhero by $1$. They can do at most $m$ operations. Also, on a particular superhero at most $k$ operations can be done.
     24 
     25 Can you help the avengers team to maximize the average power of their crew?
     26 
     27 Input
     28 
     29 The first line contains three integers $n$, $k$ and $m$ ($1 \le n \le 10^{5}$, $1 \le k \le 10^{5}$, $1 \le m \le 10^{7}$) — the number of superheroes, the maximum number of times you can increase power of a particular superhero, and the total maximum number of operations.
     30 
     31 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{6}$) — the initial powers of the superheroes in the cast of avengers.
     32 
     33 Output
     34 
     35 Output a single number — the maximum final average power.
     36 
     37 Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.
     38 
     39 Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 2 4 6
     47 4 7
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 11.00000000000000000000
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4 2 6
     60 1 3 2 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 5.00000000000000000000
     67 ```
     68 
     69 Note
     70 
     71 In the first example, the maximum average is obtained by deleting the first element and increasing the second element four times.
     72 
     73 In the second sample, one of the ways to achieve maximum average is to delete the first and the third element and increase the second and the fourth elements by $2$ each.