codeforces-scrape

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

348A.md (1488B)


      1 Source: https://codeforces.com/problemset/problem/348/A
      2 
      3 A. Mafia
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 One day *n* friends gathered together to play "Mafia". During each round of the game some player must be the supervisor and other *n* - 1 people take part in the game. For each person we know in how many rounds he wants to be a player, not the supervisor: the *i*-th person wants to play *a**i* rounds. What is the minimum number of rounds of the "Mafia" game they need to play to let each person play at least as many rounds as they want?
     22 
     23 Input
     24 
     25 The first line contains integer *n* (3 ≤ *n* ≤ 105). The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109) — the *i*-th number in the list is the number of rounds the *i*-th person wants to play.
     26 
     27 Output
     28 
     29 In a single line print a single integer — the minimum number of game rounds the friends need to let the *i*-th person play at least *a**i* rounds.
     30 
     31 Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 3  
     39 3 2 2
     40 ```
     41 
     42 Output
     43 
     44 ```
     45 4
     46 ```
     47 
     48 Input
     49 
     50 ```
     51 4  
     52 2 2 2 2
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 3
     59 ```
     60 
     61 Note
     62 
     63 You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times: http://en.wikipedia.org/wiki/Mafia_(party_game).