codeforces-scrape

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

2014C.md (2565B)


      1 Source: https://codeforces.com/problemset/problem/2014/C
      2 
      3 C. Robin Hood in Town
      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 In Sherwood, we judge a man not by his wealth, but by his merit.
     22 
     23 Look around, the rich are getting richer, and the poor are getting poorer. We need to take from the rich and give to the poor. We need Robin Hood!
     24 
     25 There are $n$ people living in the town. Just now, the wealth of the $i$-th person was $a_i$ gold. But guess what? The richest person has found an extra pot of gold!
     26 
     27 More formally, find an $a_j=max(a_1, a_2, \dots, a_n)$, change $a_j$ to $a_j+x$, where $x$ is a non-negative integer number of gold found in the pot. If there are multiple maxima, it can be any one of them.
     28 
     29 A person is unhappy if their wealth is strictly less than half of the average wealth$^{\text{∗}}$.
     30 
     31 If strictly more than half of the total population $n$ are unhappy, Robin Hood will appear by popular demand.
     32 
     33 Determine the minimum value of $x$ for Robin Hood to appear, or output $-1$ if it is impossible.
     34 
     35 $^{\text{∗}}$The average wealth is defined as the total wealth divided by the total population $n$, that is, $\frac{\sum a_i}{n}$, the result is a real number.
     36 
     37 Input
     38 
     39 The first line of input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot10^5$) — the total population.
     42 
     43 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) — the wealth of each person.
     44 
     45 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, output one integer — the minimum number of gold that the richest person must find for Robin Hood to appear. If it is impossible, output $-1$ instead.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 6
     57 
     58 1
     59 
     60 2
     61 
     62 2
     63 
     64 2 19
     65 
     66 3
     67 
     68 1 3 20
     69 
     70 4
     71 
     72 1 2 3 4
     73 
     74 5
     75 
     76 1 2 3 4 5
     77 
     78 6
     79 
     80 1 2 1 1 1 25
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 -1
     87 -1
     88 0
     89 15
     90 16
     91 0
     92 ```
     93 
     94 Note
     95 
     96 In the first test case, it is impossible for a single person to be unhappy.
     97 
     98 In the second test case, there is always $1$ happy person (the richest).
     99 
    100 In the third test case, no additional gold are required, so the answer is $0$.
    101 
    102 In the fourth test case, after adding $15$ gold, the average wealth becomes $\frac{25}{4}$, and half of this average is $\frac{25}{8}$, resulting in $3$ people being unhappy.
    103 
    104 In the fifth test case, after adding $16$ gold, the average wealth becomes $\frac{31}{5}$, resulting in $3$ people being unhappy.