codeforces-scrape

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

574A.md (2116B)


      1 Source: https://codeforces.com/problemset/problem/574/A
      2 
      3 A. Bear and Elections
      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 Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.
     22 
     23 There are *n* candidates, including Limak. We know how many citizens are going to vote for each candidate. Now *i*-th candidate would get *a**i* votes. Limak is candidate number 1. To win in elections, he must get strictly more votes than any other candidate.
     24 
     25 Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?
     26 
     27 Input
     28 
     29 The first line contains single integer *n* (2 ≤ *n* ≤ 100) - number of candidates.
     30 
     31 The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 1000) - number of votes for each candidate. Limak is candidate number 1.
     32 
     33 Note that after bribing number of votes for some candidate might be zero or might be greater than 1000.
     34 
     35 Output
     36 
     37 Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5  
     45 5 1 11 2 8
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 4
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 4  
     58 1 8 8 8
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 6
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 2  
     71 7 6
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 0
     78 ```
     79 
     80 Note
     81 
     82 In the first sample Limak has 5 votes. One of the ways to achieve victory is to bribe 4 citizens who want to vote for the third candidate. Then numbers of votes would be 9, 1, 7, 2, 8 (Limak would have 9 votes). Alternatively, Limak could steal only 3 votes from the third candidate and 1 vote from the second candidate to get situation 9, 0, 8, 2, 8.
     83 
     84 In the second sample Limak will steal 2 votes from each candidate. Situation will be 7, 6, 6, 6.
     85 
     86 In the third sample Limak is a winner without bribing any citizen.