Problem:


Score : 600 points

Problem Statement

We have a sequence of length N consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes N-1 or smaller. (The operation is the same as the one in Problem D.)

Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by N, and increase each of the other elements by 1.

It can be proved that the largest element in the sequence becomes N-1 or smaller after a finite number of operations.

You are given the sequence a_i. Find the number of times we will perform the above operation.

Constraints

2 ≤ N ≤ 50

0 ≤ a_i ≤ 10^{16} + 1000

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the number of times the operation will be performed.

Sample Input 1

4
3 3 3 3

Sample Output 1

0

Sample Input 2

3
1 0 3

Sample Output 2

1

Sample Input 3

2
2 2

Sample Output 3

2

Sample Input 4

7
27 0 0 0 0 0 0

Sample Output 4

3

Sample Input 5

10
1000 193 256 777 0 1 1192 1234567891011 48 425

Sample Output 5

1234567894848



Sample input:
4
3 3 3 3


Sample output:
0

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))

ans=0
flag=True
while flag is True:
    flag = False
    for i in range(N):
        if A[i] >= N:
            c = A[i]//N
            A[i]-=(N*c)
            ans += c
            for j in range(N):
                if j!=i:
                    A[j]+=c
            flag = True
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(i) for i in input().split()]
ans=0
while True:
  f=0
  for i in range(N):
    if a[i]>=N:
      d=a[i]//N
      ans+=d
      a[i]%=N
      for j in range(N):
        if i!=j:
          a[j]+=d
      f=1
      break
  if f==0:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

a.sort(key=lambda x: -x)
while a[0] - a[n - 1] >= n + 1:
    operation()
    a.sort(key=lambda x: -x)

phases = max(0, min(a) - n)
x += n * phases
for i in range(n):
    a[i] -= phases
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

a.sort(key=lambda x: -x)
while a[0] - a[n - 1] >= n + 1:
    operation()
    a.sort(key=lambda x: -x)

save = a[:]
difs = [a[i] - a[i - 1] for i in range(1, n)]

#print('searching for cycles', max(difs))
c = 0
while True:
    c += 1
    operation()
    a.sort(key=lambda x: -x)
    d = [a[i] - a[i - 1] for i in range(1, n)]
    #print(max(d))
    if d == difs:
        break
#print('cycle found')

i = a.index(min(a))
diff_by_c = save[i] - a[i]  # svakih c se smanji za diff_by_c
diff = max(0, a[i] - n)
phases = diff // diff_by_c
x += c * phases
for i in range(n):
    a[i] -= phases * diff_by_c
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

while a[0] - a[n - 1] >= n + 1:
    operation()
    a.sort(key=lambda x: -x)

save = a[:]
difs = [a[i] - a[i - 1] for i in range(1, n)]

#print('searching for cycles', max(difs))
c = 0
while True:
    c += 1
    operation()
    a.sort(key=lambda x: -x)
    d = [a[i] - a[i - 1] for i in range(1, n)]
    #print(max(d))
    if d == difs:
        break
#print('cycle found')

i = a.index(min(a))
diff_by_c = save[i] - a[i]  # svakih c se smanji za diff_by_c
diff = max(0, a[i] - n)
phases = diff // diff_by_c
x += c * phases
for i in range(n):
    a[i] -= phases * diff_by_c
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

for i in range(1000):
    operation()
    a.sort(key=lambda x: -x)

while a[0] - a[1] >= n:
    operation()
    a.sort(key=lambda x: -x)

save = a[:]
difs = [a[i] - a[i - 1] for i in range(1, n)]

#print('searching for cycles', max(difs))
c = 0
while True:
    c += 1
    operation()
    a.sort(key=lambda x: -x)
    d = [a[i] - a[i - 1] for i in range(1, n)]
    #print(max(d))
    if d == difs:
        break
#print('cycle found')

i = a.index(min(a))
diff_by_c = save[i] - a[i]  # svakih c se smanji za diff_by_c
diff = max(0, a[i] - n)
phases = diff // diff_by_c
x += c * phases
for i in range(n):
    a[i] -= phases * diff_by_c
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

while a[0] - a[1] >= n:
    operation()
    a.sort(key=lambda x: -x)

save = a[:]
difs = [a[i] - a[i - 1] for i in range(1, n)]

#print('searching for cycles', max(difs))
c = 0
while True:
    c += 1
    operation()
    d = [a[i] - a[i - 1] for i in range(1, n)]
    #print(max(d))
    if d == difs:
        break
#print('cycle found')

i = a.index(min(a))
diff_by_c = save[i] - a[i]  # svakih c se smanji za diff_by_c
diff = max(0, a[i] - n)
phases = diff // diff_by_c
x += c * phases
for i in range(n):
    a[i] -= phases * diff_by_c
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())


def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    a = ILI()
    return (N, a)


def check_a(N, a):
    for i, _a in enumerate(a):
        if _a >= N:
            return i
    return -1


def solve(N, a):
    ans = 0
    while True:
        ret_ind = check_a(N, a)
        if ret_ind == -1:
            break
        div, mod = divmod(a[ret_ind], N)
        for i in range(N):
            if i == ret_ind:
                a[i] = mod
                continue
            a[i] += div
        ans += div

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

for i in range(100):
    operation()

save = a[:]
difs = [a[i] - a[i - 1] for i in range(1, n)]

#print('searching for cycles', max(difs))
c = 0
while True:
    c += 1
    operation()
    d = [a[i] - a[i - 1] for i in range(1, n)]
    #print(max(d))
    if d == difs:
        break
#print('cycle found')

i = a.index(min(a))
diff_by_c = save[i] - a[i]  # svakih c se smanji za diff_by_c
diff = max(0, a[i] - n)
phases = diff // diff_by_c
x += c * phases
for i in range(n):
    a[i] -= phases * diff_by_c
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, key=lambda x: -x)
x = (a[0] - a[1]) // (n + 1)

def check():
    global a
    global x
    if max(a) <= n - 1:
        print(x)
        exit(0)

def operation():
    global a
    global x
    x += 1
    i = a.index(max(a))
    for j in range(n):
        if j != i:
            a[j] += 1
    a[i] -= n
    check()

a[0] -= x * n
for i in range(1, n):
    a[i] += x
check()

for i in range(1000):
    operation()

save = a[:]
difs = [a[i] - a[i - 1] for i in range(1, n)]

#print('searching for cycles', max(difs))
c = 0
while True:
    c += 1
    operation()
    d = [a[i] - a[i - 1] for i in range(1, n)]
    #print(max(d))
    if d == difs:
        break
#print('cycle found')

i = a.index(min(a))
diff_by_c = save[i] - a[i]  # svakih c se smanji za diff_by_c
diff = max(0, a[i] - n)
phases = diff // diff_by_c
x += c * phases
for i in range(n):
    a[i] -= phases * diff_by_c
check()

while True:
    operation()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
inf = 1000000000000000000
ans = inf
def okay(nd, debug=False):
    tot = 0
    dp = [ [ -1 for i in range(n) ] for j in range(n+1) ]
    dp[0][0] = 0
    for i in range(n):
        bl,br,ba=0,nd,inf
        while bl <= br:
            bm = (bl + br) // 2
            if a[i] - bm * n + (nd - bm) < n:
                ba = bm
                br = bm - 1
            else:
                bl = bm + 1
        if debug:
            print(i, ba)
        for j in range(n):
            if dp[i][j] == -1:
                continue
            for k in range(n):
                tdp = dp[i][j] + ba + k
                if tdp > nd:
                    continue
                if dp[i+1][tdp % n] == -1 or tdp < dp[i+1][tdp % n]:
                    dp[i+1][tdp % n] = tdp
    if dp[n][nd % n] == -1:
        return False
    return dp[n][nd % n] <= nd
for sft in range(0,n):
    l,r,ta=0,inf,inf
    while l <= r:
        m = (l + r) // 2
        if okay(m*n + sft):
            ta = m*n + sft
            r = m - 1
        else:
            l = m + 1
    # print(sft, ta)
    ans=min(ans,ta)
# okay(1234567894848, True)
# okay(ans, True)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
m = min(A)
cnt = 0
while max(A) >= n:
  temp = 0
  for i in range(n):
    t = (A[i]+1)//(n+1)
    temp += t
    A[i] -= t*(n+1)
  for i in range(n):
    A[i] += temp
  cnt += temp
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

ans = 0
while True:
    add = 0
    B = [0] * N
    cut = [0] * N
    for i, a in enumerate(A):
        d, m = divmod(a, N)
        B[i] = m
        cut[i] = d
        add += d

    for i, c in enumerate(cut):
        B[i] += add - c

    if not add:
        break

    ans += add
    A = B

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *
from math import ceil
input = sys.stdin.readline
N = int(input())
H = []
for a in list(map(int, input().split())):
    heappush(H,-a)
off = 0
while True:
    x = heappop(H)
    a = -x+off
    if a<=N-1: print(off); exit()
    cnt = ceil(max(a-(N-1), 0)/(N+1))
    a -= cnt*(N+1)
    heappush(H,off-a)
    off += cnt

Submission status: Accepted

Solution code:
def ok(N, A):
    return all([a <= N - 1 for a in A])


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    while not ok(N, A):
        n = 0
        # 「全てに1を足して、特定のものからN+1を引く」で等価な操作になる
        for i in range(N):
            c = A[i] // N
            n += c
            A[i] -= c * (N + 1)
        for i in range(N):
            A[i] += n
        ans += n
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())
As = list(map(int, input().split()))

def check():
    return all([a <= N-1 for a in As])

ans = 0
while not check():
    n = 0
    for i in range(N):
        a = As[i]
        t = a // N
        n += t
        As[i] -= t * (N+1)
    for i in range(N):
        As[i] += n
    ans += n
print(ans)

Submission status: Accepted

Solution code:
def main(n,a):
  b=[-x for x in a]
  b.sort()
  from heapq import heappop,heappush,heapify
  heapify(b)
  ans=-1
  for i in range(n+2):
    v=heappop(b)
    if -v<=n-1:
      ans=i
      break
    b=[x-1 for x in b]
    v+=n
    heappush(b,v)
  if ans>=0:return ans
  suma=sum(a)
  # mod (n+1)で考える
  am=[x%(n+1) for x in a]
  sumam=0
  for i in range(n+1):
    am=[(x+1)%(n+1) for x in am]
    if max(am)<=n-1:
      sumam=max(sum(am),sumam)
  ans=suma-sumam
  return ans


n=int(input())
a=list(map(int,input().split()))
print(main(n,a))

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))

ok,ng=(10**16+1000)*n,-1
while ok-ng>1:
    mid=(ok+ng)//2
    cnt=0
    for i in range(n):
        cnt+=celi(a[i]+mid-n+1,n+1)
    if cnt<=mid:
        ok=mid
    else:
        ng=mid
    # print(ok,ng)
# print(ok)
# print(sum(a)-(n-1)*n)
tmp=sum(a)-(n-1)*n
for i in range(max(0,tmp),ok+1):
    cnt=0
    for j in range(n):
        cnt+=celi(a[j]+i-n+1,n+1)
    if cnt<=i:
        print(i)
        break

Submission status: Accepted

Solution code:
import numpy as np
I,S=input,sum
n,c=int(I()),0
a=np.array(list(map(int, I().split())))
while max(a)>=n:f=a//n;S=sum(f);a=a-f*n+(S-f);c+=sum(f)
print(c)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))


def is_possible(C):
    res = 0
    for x in A:
        if x+C - N >= 0:
            res += (x+ C - N)//(N+1) + 1
    #print(res,C)
    return int(res <= C)

l = 0  # impossible
r = 10**30  # possible

while r - l > 1:
    M = (l+r)//2
    if is_possible(M)>0:
        r = M
    else:
        l = M
for i in range(10**5,-1,-1):
    if is_possible(r -i):
        print(r-i)
        break

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))


def is_possible(C):
    res = 0
    for x in A:
        if x+C - N >= 0:
            res += (x+ C - N)//(N+1) + 1
    #print(res,C)
    return int(res <= C)

l = 0  # impossible
r = 10**30  # possible
is_possible(1234567894848)
while r - l > 1:
    M = (l+r)//2
    if is_possible(M)>0:
        r = M
    else:
        l = M
for i in range(10**5,-1,-1):
    if is_possible(r -i):
        print(r-i)
        break

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

def check_x(x):
    s = 0
    for a in A:
        b = a+x
        s += b//(N+1) + (b%(N+1))//N
    return s<=x

def check(z):
    ok = False
    for x in range(z, max(-1, z-N), -1):
        ok = ok or check_x(x)
    return ok

min_ok = 10**20
max_ng = -1

while min_ok-max_ng>1:
    tgt = (min_ok+max_ng)//2
    if check(tgt):
        min_ok = tgt
    else:
        max_ng = tgt

print(min_ok)

Submission status: Accepted

Solution code:
N, *A = [int(_) for _ in open(0).read().split()]
sumB = max(0, sum(A) - N * (N - 1))
while True:
    B = [0 - (-(a + sumB + 1 - N)) // (N + 1) for a in A]
    if sumB == sum(B):
        break
    sumB += 1
print(sumB)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(_) for _ in input().split()])
#B[i]回の操作をすると全項N-1以下になる
#A[i]-N*B[i]+sum(B)-B[i]<=N-1 が全iで成り立つ
#B[i]=0-(-(a+x+1-N))//(N+1)

def check(x):
    b = [0 - (-(a + x + 1 - N)) // (N + 1) for a in A]
    return sum(b) == x

p = max(0, sum(A) - (N - 1) * N)
while True:
    q = check(p)
    if q:
        break
    p += 1
print(p)

Submission status: Accepted

Solution code:
n = int(input())
A = list(int(x) for x in input().split())
ans = 0
while max(A) >= n:
    m = max(A)
    index = A.index(m)
    count = m // n
    ans += count
    A = [a + count for a in A]
    A[index] -= n * count + count

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import ceil

n = readint()
a = readints()

ans = 0
for i in range(n):
    a.sort()
    if a[-1]<n:
        break
    ans += 1
    for j in range(n-1):
        a[j]+=1
    a[-1]-=n

a.sort()
while a[-1]-a[0]>n+1:
    x = ceil((a[-1]-a[0]-n-1)/(n+1))
    ans += x
    for j in range(n-1):
        a[j] += x
    a[-1] -= n*x
    a.sort()
if a[-1]>=n:
    ans += (a[0]-n+1)*n
    A = a[0]
    for i in range(n):
        a[i] -= A-n+1

while a[-1]>=n:
    ans += 1
    for j in range(n-1):
        a[j]+=1
    a[-1]-=n
    a.sort()

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import ceil

n = readint()
a = readints()

ans = 0
for i in range(n):
    a.sort()
    if a[-1]<n:
        break
    ans += 1
    for j in range(n-1):
        a[j]+=1
    a[-1]-=n

a.sort()
while a[-1]-a[0]>n+1:
    x = ceil((a[-1]-a[0]-n-1)/(n+1))
    ans += x
    for j in range(n-1):
        a[j] += x
    a[-1] -= n*x
    a.sort()
if a[-1]>n:
    ans += (a[0]-n+1)*n
    A = a[0]
    for i in range(n):
        a[i] -= A-n+1

while a[-1]>=n:
    ans += 1
    for j in range(n-1):
        a[j]+=1
    a[-1]-=n
    a.sort()

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
list_of_a = list(map(int, input().split()))

ng = max(0, sum(list_of_a)-(N-1)*N) - 1
ok = max(0, (max(list_of_a) - (N-1)) * N)
while ok - ng > 1:
    mid = (ok + ng) // 2
    count = 0
    for a in list_of_a:
        count += (a + mid + 1) // (N+1)
    if count <= mid:
        ok = mid
    else:
        ng = mid

#'ok'-i (i=1..N) may be better

for i in range(0, 30 * N + 1):
    mid = ok - i
    if mid < 0:
        break
    count = 0
    for a in list_of_a:
        count += (a + mid + 1) // (N+1)
    if count == mid:
        ans = mid

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#k, = map(int,read().split())

def make(k):
    if k==0:
        print(1)
        print(0)
        exit()
    
    k -= 1
    n = 50
    q = k//n
    r = k%n
    
    a = [(2*n-1)+q]*n
    for i in range(r):
        for j in range(n):
            if i==j: a[j] += n
            else: a[j] -= 1
        
    print(n)
    print(*a)


def judge(n,a):
    if max(a) < n:
        return 0
    
    ans = 0
    for i in range(n):
        if a[i] > 3*n:
            d = (a[i]-3*n)//(n+1)
            ans += d
            a[i] -= d*(n+1)
    
    #print(ans)
    if ans >= 2*n:
        ans += n*ans    
    else:
        for i in range(n):
            a[i] += ans

    #print(ans,a)
    #return
    
    while True:
        if max(a) < n:
            return ans
        
        idx = max(range(n),key=lambda i:a[i])
        for j in range(n):
            a[j] += 1
        a[idx] -= n+1
        ans += 1
        #print(idx,a)


n,*a = map(int,read().split())

print(judge(n,a))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))
    a.sort(reverse=True)

    ans = 0
    flag = True

    while flag:
        flag = False
        cur = 0
        for i in range(n):
            if a[i] > (n - 1):
                cnt = (a[i] - (n - 1) + (n - 1)) // n
                ans += cnt
                cur += cnt
                a[i] -= (n + 1) * cnt
        for i in range(n):
            a[i] += cur
            if a[i] > n - 1:
                flag = True

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
ans = 0
while a[np.argmax(a)] >= n:
    temp = a[np.argmax(a)] // n
    ans += temp
    a += temp
    a[np.argmax(a)] -= (n+1) * temp
print(ans)

Submission status: Accepted

Solution code:
n,a=open(0);n=int(n)+1;d,A,q=[0]*n+[1],1e+18,0
for b in a.split():b=int(b);q+=(b+1)//n;d[(b+1)%n]+=1
for r in range(n):q+=d[n-r]-1;A=min(A,max(q,0)*n+r)
print(A)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ans = 0
while any(a[i] >= n for i in range(n)):
    res = [-(-(a[i] - n + 1) // n) for i in range(n)]
    x = sum(res)
    a = [a[i] + x - (n + 1) * res[i] for i in range(n)]
    ans += x
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
if max(A) < N:
  print(0)
  quit()

ans = 0
while max(A) >= N:
  times = [0] * N
  for i, a in enumerate(A):
    t = -(-(a - (N-1))//N)
    A[i] -= t*N
    times[i] = t
  total = sum(times)
  ans += total
  for i in range(N):
    A[i] += total - times[i]

print(ans)

Submission status: Accepted

Solution code:
import math
def main():
    n = int(input())
    l = list(map(int, input().split()))
    c = 0
    while max(l) > n-1:
        l.sort(reverse=True)
        tc = [0] * n
        for i in range(n):
            if l[i] >= n:
                tc[i] = math.ceil((l[i] - n + 1)/n)
                l[i] -= tc[i] * n
        stc = sum(tc)
        for i in range(n):
            l[i] += stc - tc[i]
        c += stc
    return c
print(main())

Submission status: Accepted

Solution code:
n=int(input())+1;a=list(map(int,input().split()));d,A,q=[0]*n,0,0
for i in range(n-1):
    q+=(a[i]+1)//n;d[(a[i]+1)%n]+=1
A=q*n
for r in range(1,n):
    q+=d[n-r]-1;A=min(A,max(q,0)*n+r)
print(A)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(input().split(), np.int64)


def check(x):
    cnt = np.maximum((a + x + 1) // (n + 1), 0)
    return cnt.sum() <= x


l = -1
r = 10 ** 18

while r - l > 1:
    m = (l + r) // 2
    if check(m):
        r = m
    else:
        l = m

for i in range(max(r - (n - 1) * n, 0), r + 1):
    if check(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(input().split(), np.int64)


def check(x):
    cnt = np.maximum((a + x + 1) // (n + 1), 0)
    return cnt.sum() <= x


l = -1
r = 10 ** 18

while r - l > 1:
    m = (l + r) // 2
    if check(m):
        r = m
    else:
        l = m

for i in range(max(r - n * n, 0), r + 1):
    if check(i):
        print(i)
        exit()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

i = 0
ans = 0
while max(a) >= n:
    if a[i] >= n:
        cnt = a[i] // n
        ans += cnt
        a[i] -= n * cnt
        for j in range(n):
            if j == i:
                continue
            a[j] += cnt

    i = (i + 1) % n

print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
ans=0
while True:
	div=[x//n for x in a]
	ps=sum(div)
	ans+=ps
	if not ps:
		break
	a=[x-(n+1)*d+ps for x,d in zip(a,div)]
print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = sorted(getlist())
	cnt = 0

	while True:
		if A[-1] <= N - 1:
			print(cnt)
			return
		if (A[-1] - (N - 1)) % N == 0:
			K = int((A[-1] - (N - 1)) // N)
		else:
			K = int((A[-1] - (N - 1)) // N) + 1
		
		#処理
		cnt += K
		A[-1] -= K * N
		for i in range(N - 1):
			A[i] += K
		A = sorted(A)

	print(cnt)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))

ans = 0
while max(a) >= N:
    for i in range(N):
        if a[i] >= N:
            tmp = a[i] // N
            for j in range(N):
                if j == i:
                    a[j] -= tmp*N
                else:
                    a[j] += tmp
            ans += tmp

print(ans)

Submission status: Accepted

Solution code:
# ARC079E
n = int(input())
a = list(map(int, input().split()))

def sub(n, a):
    # aを現時点で必要なだけ叩いて、その回数と終わったあとの状態
    c = 0
    nums = [0] * n
    for i,num in enumerate(a):
        if num> n-1:
            v = (num - (n-1)) // n + bool((num - (n-1)) % n)
            a[i] = num - v*n
            nums[i] -= v
            c += v
    return c, [c+num+num2 for num,num2 in zip(a, nums)]

count = 0
while max(a)>=n:
    c, a = sub(n, a)
    count += c
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

count = 0
flag = True

while flag:
    c = [0]*N
    for i in range(N):
        c[i] = A[i]//N
        A[i] %= N
    S = sum(c)
    flag = False
    for i in range(N):
        A[i]+=S-c[i]
        if A[i]>=N:
            flag=True
    count += S

print(count)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
while max(a) >= n:
    count = 0
    for i in range(n):
        count += a[i]//n
        a[i] = a[i]%n - a[i]//n
    for i in range(n):
        a[i] += count
    ans += count
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))

data=[0 for i in range(N+1)]
ans=0
q=0
for i in range(N):
    q+=(a[i]+1)//(N+1)
    data[(a[i]+1)%(N+1)]+=1
ans=q*(N+1)

for r in range(1,N+1):
    q+=data[N+1-r]-1
    t=max(q,0)*(N+1)+r
    ans=min(ans,t)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
ans=float("inf")
for r in range(0,N+1):
    test=0
    for j in range(0,N):
        test+=(a[j]+r+1)//(N+1)
    test-=r
    t=max(test,0)*(N+1)+r
    ans=min(ans,t)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
alist=list(map(int,input().split()))
#print(alist)

answer=0
while max(alist)>=N:
  s=sum([a//N for a in alist])
  for i in range(N):
    dec=(alist[i]//N)*N    
    asc=s-(alist[i]//N)
    alist[i]-=dec-asc
  answer+=s
  
print(answer)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 操作：c回と固定すると，
# 各要素を何回以上選ぶ必要があるかわかる
# c→c+(N+1) とすると，必要回数の和が+Nになることから，
# 最小のc(mod N+1)がわかる

def ceil(x,y):
    return x//y + int(x%y != 0)

N = I()
a = LI()

ans = float('inf')
for c in range(N+1):
    need = 0
    for i in range(N):
        need += max(0,ceil(c+a[i]-(N-1),N+1))
    if need <= c:
        temp = c
    else:
        temp = c+(need-c)*(N+1)
    if temp < ans:
        ans = temp

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline

N, *a = map(int, read().split())
heap = [-i for i in a]
heapify(heap)
answer = 0
while True:
    if -heap[0] + answer < N:
        break
    i = -heappop(heap) + answer
    cnt = (i + 1) // (N + 1)
    i -= answer + cnt * (N + 1)
    answer += cnt
    heappush(heap, -i)
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
ans=0
while True:
	for i in range(n):
		r=a[i]//n
		a[i]%=n
		a[i]-=r
		cnt+=r
	ans+=cnt
	if cnt==0:
		break
	for i in range(n):
		a[i]+=cnt
	cnt=0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

ans = 0
while any(a > N - 1 for a in A):
    S = sum(a // N for a in A)
    A = [a + (S - a // N) - (a // N) * N for a in A]
    ans += S

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
count = 0

while max(a) >= N:
    plus = 0

    for i in range(N):
        plus += a[i] // N
        a[i] = a[i] % N - a[i] // N

    count += plus
    for j in range(N):
        a[j] += plus

print(count)

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
count=0
while(1):
	K=max(L)
	if max(L)<N:
		print(count)
		exit()
	else:
		tmp=0
		#print(max(L))
		M=K//N
		count+=M
		for i in range(N):
			if L[i]==K and tmp==0:
				#print(i)
				tmp=1
				L[i]=K%N
			else:
				L[i]+=M
		#print(L)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

ans = 0
while max(A) >= N:
    i = A.index(max(A))
    k = A[i] // N
    A[i] %= N
    ans += k
    for j in range(N):
        if j != i:
            A[j] += k
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
a = LIST()
ans = 0
while any([x >= N for x in a]):
	S = sum([x//N for x in a])
	for i in range(N):
		tmp = a[i]//N  # i番目の要素に対する操作回数
		a[i] -= N*tmp
		a[i] += (S-tmp)
		ans += tmp

print(ans)