Codeforces Round #202 (Div. 1), problem: (A) Mafia:
http://codeforces.com/problemset/problem/348/A
Codeforces Round #202 (Div. 1), problem: (A) Mafia editorial:
http://codeforces.com/blog/entry/9031
Codeforces Round #202 (Div. 1), problem: (A) Mafia solution: http://ideone.com/JEoXON
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
long long int n, a, ma=0, cnt=0;
scanf("%I64d", &n);
for(int i=0; i<n; i++) {
scanf("%I64d", &a);
if(a>ma) ma=a;
cnt+=a;
}
a=ceil((double)cnt/(n-1)), a=max(a, ma);
printf("%I64d", a);
return 0;
}
note, courtesy of
baklazan:
http://codeforces.com/blog/entry/9031#comment-147355
Let's say you're going to play x games. If someone wanted to play more than x games, he wouldn't be able to do so, so he would be unhappy. Therefore, if everyone is happy, x ≥ ai must hold for each i, so
x ≥ max(a1, a2, ..., an)
Let $b_i$ be number of games, where i-th player is supervisor and let ci be number of games, where he plays. In each game i-th player is playing, XOR supervising, so ci + bi = x. Also, he wants to play at least ai games, soai ≤ ci, thus bi ≤ ci + bi - ai, so bi ≤ x - ai.
Each game is supervised by one player, so x = b1 + b2 + ... + bn. Giving it all together:
x = b1 + b2 + ... + bn ≤ (x - a1) + (x - a2) + ... + (x - an)
Now we have two lower bounds for $x$ . Smallest x satisfying both of them is
This number of games is enough, because if first $x - a_1$ games are supervised by first player, next x - a2games are supervised by second player etc., until the x-th game, then everyone plays enough games and each game is supervised by someone.
