Problem:


Score : 200 points

Problem Statement

There are K pieces of cakes.
Mr. Takahashi would like to eat one cake per day, taking K days to eat them all.

There are T types of cake, and the number of the cakes of type i (1 ≤ i ≤ T) is a_i.  

Eating the same type of cake two days in a row would be no fun,
so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before.  

Compute the minimum number of days on which the same type of cake as the previous day will be eaten.

Constraints

1 ≤ K ≤ 10000

1 ≤ T ≤ 100

1 ≤ a_i ≤ 100

a_1 + a_2 + ... + a_T = K

Input

The input is given from Standard Input in the following format:

K T
a_1 a_2 ... a_T

Output

Print the minimum number of days on which the same type of cake as the previous day will be eaten.

Sample Input 1

7 3
3 2 2

Sample Output 1

0

For example, if Mr. Takahashi eats cakes in the order of 2, 1, 2, 3, 1, 3, 1, he can avoid eating the same type of cake as the previous day.

Sample Input 2

6 3
1 4 1

Sample Output 2

1

There are 6 cakes.
For example, if Mr. Takahashi eats cakes in the order of 2, 3, 2, 2, 1, 2, he has to eat the same type of cake (i.e., type 2) as the previous day only on the fourth day.
Since this is the minimum number, the answer is 1.

Sample Input 3

100 1
100

Sample Output 3

99

Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.



Sample input:
7 3
3 2 2


Sample output:
0

Submission status: Wrong Answer

Solution code:
K,T=map(int,input().split())
a=list(map(int,input().split()))
b=[]

for i,an in enumerate(a):
    b.append([an,i])
ex = -1
ans = 0

if T == 1:
	print(K-1)
else:
  for i in range(K):
    list.sort(b, reverse=True)
    if ex == b[0][1] and b[1][0] != 0:
      b[1][0] -= 1
      ex = b[1][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
    else:
      b[0][0] -= 1
      if ex == b[0][1]:
        ans+=1
      ex = b[0][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
    print(ans)

Submission status: Wrong Answer

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

maxi=max(a)
other = sum(a)-maxi
print(maxi,other)

if maxi<=other:
    print(0)
else:
    print(maxi-other-1)

Submission status: Wrong Answer

Solution code:
K,T=map(int,input().split())
a=list(map(int,input().split()))
b=[]

for i,an in enumerate(a):
    b.append([an,i])
ex = -1
ans = 0

if T == 1:
	print(K-1)
else:
  for i in range(K):
    list.sort(b, reverse=True)
    if ex == b[0][1] and b[0][0] == b[1][0]:
      b[1][0] -= 1
    else:
      b[0][0] -= 1
      if ex == b[0][1]:
        ans+=1
      ex = b[0][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
    print(ans)

Submission status: Wrong Answer

Solution code:
K,T=map(int,input().split())
a=list(map(int,input().split()))
b=[]

for i,an in enumerate(a):
    b.append([an,i])
ex = -1
ans = 0

if T == 1:
	print(K-1)
else:
  for i in range(K):
    list.sort(b, reverse=True)
    if ex == b[0][1] and b[0][0] == b[1][0]:
      b[1][0] -= 1
    else:
      b[0][0] -= 1
      if ex == b[0][1]:
        ans+=1
        print(b)
      ex = b[0][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
      print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
k,t = map(int,input().split())
a = list(map(int,input().split()))
mx = max(a)
others = k - mx
if t == 1:
    print(k - 1)
    exit()

if others >= mx - 1:
    print(0)
else:
    print(others - 1)

Submission status: Wrong Answer

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

ans = max(a)

for i in a:
    if i != max(a):
        ans -= i
print(max(0, ans))

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
if max(a)%2 == 1:
    print(max(a)-t)
else:
    print(max(a)-1-t)

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
print(max(a)-t)

Submission status: Wrong Answer

Solution code:
K,T=map(int,input().split())
a=list(map(int,input().split()))
print(max(a)-(K-max(a))-1,0)

Submission status: Wrong Answer

Solution code:
k, _, *a = map(int, open(0).read().split())
print(max(b*2 - k - 1 for b in a))

Submission status: Wrong Answer

Solution code:
def min_day(A,K,T):
    if T == 1:
        return K-1
    else:
        A_max = max(A)
        times = A_max // (K-A_max)
        if A_max % (K-A_max) == 0:
            times -= 1

        return times

def main():
    K,T = map(int,input().split())
    A = list(map(int,input().split()))

    print(min_day(A,K,T))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
k,t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
a = deque(a)
length = len(a)
if length ==1:
    print(sum(a)-1)
    exit()
while length > 1:
    mx = a.pop()
    mn = a.popleft()
    mx -= 1
    mn -= 1
    if mx != 0:
        a.append(mx)
    else:
        length -=1
    if mn != 0:
        a.appendleft(mn)
    else:
        length-=1    
print(sum(a)-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
k,t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
a = deque(a)
length = len(a)
if length ==1:
    print(sum(a))
    exit()
while length > 1:
    mx = a.pop()
    mn = a.popleft()
    mx -= 1
    mn -= 1
    if mx != 0:
        a.append(mx)
    else:
        length -=1
    if mn != 0:
        a.appendleft(mn)
    else:
        length-=1    
print(sum(a)-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
k,t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
a = deque(a)
length = len(a)
while length > 1:
    mx = a.pop()
    mn = a.popleft()
    mx -= 1
    mn -= 1
    if mx != 0:
        a.append(mx)
    else:
        length -=1
    if mn != 0:
        a.appendleft(mn)
    else:
        length-=1    
print(sum(a)-1)

Submission status: Wrong Answer

Solution code:
K,T = map(int,input().split())
t = list(map(int,input().split()))
t1 = sorted(t,reverse=True)
if T == 1:
    print(K - 1)
elif t1[0] == t1[1]:
    print(0)
elif t1[0] - t1[1] <= T - 1:
    print(0)
else:
    print(t1[0] - t1[1] - (T - 1))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b
from heapq import heapify, heappop, heappush
k, t = map(int, input().split())
nums = [int(i) for i in input().split()]
heapify(nums)

while len(nums) > 2:
    a = heappop(nums)
    b = heappop(nums)
    c = a + b
    if c % 2 == 0:
        c = c // 2
    else:
        c = c // 2 + 1
    heappush(nums, c)

if len(nums) == 2:
    ans = (nums[1] - nums[0]) // 2
else:
    ans = k - t
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
def solve():
    K,T = map(int,input().split())
    inputa = list(map(int,input().split()))
    a = []
    for i in range(T):
        a.append((-inputa[i], a))

    heapq.heapify(a)

    prev_type = -1
    cnt = 0
    for i in range(K):
        rest,choco_type  = heapq.heappop(a)
        if prev_type == choco_type:
            if len(a) == 0:
                cnt += -rest
            else:
                rest2, choco_type2 = heapq.heappop(a)
                heapq.heappush(a,(rest,choco_type))
                rest = rest2
                choco_type = choco_type2

        if rest != 0:
            heapq.heappush(a, (rest+1, choco_type))
        
        prev_type = choco_type
    
    print(cnt)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import heapq
def solve():
    K,T = map(int,input().split())
    inputa = list(map(int,input().split()))
    a = []
    for i in range(T):
        a.append((-inputa[i], a))

    heapq.heapify(a)

    prev_type = -1
    cnt = 0
    for i in range(K):
        rest,choco_type  = heapq.heappop(a)
        if prev_type == choco_type:
            if len(a) == 0:
                cnt += 1
            else:
                rest2, choco_type2 = heapq.heappop(a)
                heapq.heappush(a,(rest,choco_type))
                rest = rest2
                choco_type = choco_type2

        if rest != 0:
            heapq.heappush(a, (rest+1, choco_type))
        
        prev_type = choco_type
    
    print(cnt)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

B = []
for i in range(t):
    B += [i]*A[i]

B.reverse()
L = [-1]*k
for i in range(k):
    if i%2 == 0:
        continue
    else:
        L[i] = B.pop()

for i in range(k):
    if i%2 == 1:
        continue
    else:
        L[i] = B.pop()

#print(L)
ans = 0
for i in range(1, k):
    if L[i-1] == L[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

k, t, *a = map(int, read().split())
x, y = 0, 0
for aa in a:
    if x > y:
        y += aa
    else:
        x += aa
print(abs(x - y) - 1)

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
n = abs(2 * max(a) - sum(a) )
if n <= 1:
    print(0)
else:
    print(n - 1)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())

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


ans=0
for i in range(t):
    ans+=max(0,a[i]-t)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline

K, T = map(int, readline().split())
A = list(map(int, readline().split()))

B = [-1 for _ in range(K)]

j = 0
for i, a in enumerate(A):
    for _ in range(a):
        if j <= K // 2 - 1:
            B[2 * j] = i
        else:
            B[2 * (j - K // 2) - 1] = i
        j += 1

cnt = 0
for i in range(1, K):
    if B[i - 1] == B[i]:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
k, t = map(int, input().split())
a = list(map(int, input().split()))
q = []
for i in range(t):
  q += [[a[i], str(i)]]
q = sorted(q, reverse=True)
s = ""
q = deque(q)
cake, idx = q.popleft()
s += idx
q += [[cake-1, idx]]

ans = 0 
while q:
  cake, idx = q.popleft() 
  if s[-1] == idx:
    ans += 1  
  s += idx 
  if cake-1 > 0:
    q += [[cake-1, idx]]

print(ans)

Submission status: Wrong Answer

Solution code:
k,t = map(int, input().split())
al = list(map(int, input().split()))

al.sort(reverse=True)

x,y = 0,0
for a in al:
    if x<y:
        x += a
    else:
        y += a

res = (max(x,y)-min(x,y)) - 1
print(res)

Submission status: Wrong Answer

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

print(max(0,(max(a)-1)//(k-max(a)+1)))

Submission status: Wrong Answer

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

print((max(a)-1)//(k-max(a)+1))

Submission status: Wrong Answer

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
# print('A', A)

for i in range(len(A)):
    for j in range(i + 1, len(A)):
        if A[i] == 0:
            break
        v = min(A[i], A[j])
        A[i] -= v
        A[j] -= v

print(max(A) - 1)

Submission status: Wrong Answer

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
# print('A', A)

for i in range(len(A)):
    for j in range(i + 1, len(A)):
        if A[j] == 0:
            break
        v = min(A[i], A[j])
        A[i] -= v
        A[j] -= v

print(max(A) - 1)

Submission status: Wrong Answer

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
# print('A', A)

for i in range(len(A)):
    if A[i] > 0:
        j = i + 1
        for j in range(i + 1, len(A)):
            if A[j] == 0:
                break
            v = min(A[i], A[j])
            A[i] -= v
            A[j] -= v

print(max(A) - 1)

Submission status: Wrong Answer

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

M = max(a)
if M <= (K + 2 - 1) // 2:
    ans = 0
else:
    ans = K // (K - M + 1) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
rr = range


def read_ints():
    return list(map(int, read().split()))


K, T = read_ints()
A = read_ints()
if T == 1:
    # コーナーケース
    print(K - 1)
    exit()

# 差が最も少なくなるように二分割すれば良い
# 二分探索でもいいが線形探索で愚直に合計値を計算しても十分間に合う
A.sort()
ans = 2**31
for i in rr(1, T):
    r = sum(A[:i])
    l = sum(A[i:])
    ans = min(ans, abs(r - l))
print(ans - 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    k, t = LI()
    a = LI()
    dp = [0] * (k + 1)
    dp[0] = 1
    for ai in a:
        for i in range(k, ai - 1, -1):
            dp[i] |= dp[i - ai]
    ans = inf
    for i in range(k + 1):
        if dp[i]:
            ans = min(ans, max(k - i - i,i - (k - i)))
    print(ans-1)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())

A = list(map(int, input().split()))

max_a = max(A)

if t == 1:
    print(k - 1)
elif sum(A) - max_a >= max_a:
    print(0)
else:
    print((sum(A) - max_a) - 1)

Submission status: Wrong Answer

Solution code:
N = list(map(int, input().split()))
Q = list(map(int, input().split()))
maxQ = max(Q)
rest = N[0] - 1
print(max([maxQ-rest-1, 0]))

Submission status: Wrong Answer

Solution code:
import sys

k,n=map(int,input().split())
a=list(map(int,input().split()))
a=[[a[i],i] for i in range(n)]

if n==1: print(a[0][0]-1);sys.exit()

pre=-1
ans=0
for _ in range(k):
    a.sort(reverse=True)
    if a[0][1]!=pre:
        pre=a[0][1]
        a[0][0]-=1
    elif a[1][0]>0:
        a[1][0]-=1
        pre=a[1][0]
    else:
        ans=a[0][0]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
res = sum(A) - max(A)
a = max(A)
if T == 1:
    print(K - 1)
    exit()
a -= res
cnt = 0
while a > 0:
    a -= (res+1)
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
m=max(a)
n=k-m
print(min(m-n-1,0))

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def can_set(al_max ,k,cc):
	a=al_max
	aa=((k//(cc+1))*cc) + (k%(cc+1))
	#pa((a,cc,aa))
	if a <= aa:
		return True
	return False

def main():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	pa(al)
	
	#if al[0] <= (k+1)//2:
	#	return 0
	#if al[0] == k:
	#	return k-1
	al_max=al[0]
	ng=1
	ok=k
	for i in range(1,k+1):
		if can_set(al_max,k,i):
			return i-1-1
	

def main2():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	ttt=[0]*k
	p=0
	for i, v in enumerate(al):
		for _ in range(v):
			ttt[p]=i
			p+=2
			if p >= k:
				p=1
	
	cc=0
	pre=-1
	for v in ttt:
		if pre == v:
			cc+=1
		else:
			pre=v
			
	return cc
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def can_set(al_max ,k,cc):
	a=al_max
	aa=((k//(cc+1))*cc) + (k%(cc+1))
	#pa((a,cc,aa))
	if a <= aa:
		return True
	return False

def main():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	pa(al)
	
	#if al[0] <= (k+1)//2:
	#	return 0
	#if al[0] == k:
	#	return k-1
	al_max=al[0]
	ng=1
	ok=k
	for i in range(1,k+1):
		if can_set(al_max,k,i):
			return i-1+1
	

def main2():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	ttt=[0]*k
	p=0
	for i, v in enumerate(al):
		for _ in range(v):
			ttt[p]=i
			p+=2
			if p >= k:
				p=1
	
	cc=0
	pre=-1
	for v in ttt:
		if pre == v:
			cc+=1
		else:
			pre=v
			
	return cc
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def can_set(al_max ,k,cc):
	a=al_max
	aa=((k//(cc+1))*cc) + (k%(cc+1))
	#pa((a,cc,aa))
	if a <= aa:
		return True
	return False

def main():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	pa(al)
	
	#if al[0] <= (k+1)//2:
	#	return 0
	#if al[0] == k:
	#	return k-1
	al_max=al[0]
	ng=1
	ok=k
	for i in range(1,k+1):
		if can_set(al_max,k,i):
			return i-1
	

def main2():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	ttt=[0]*k
	p=0
	for i, v in enumerate(al):
		for _ in range(v):
			ttt[p]=i
			p+=2
			if p >= k:
				p=1
	
	cc=0
	pre=-1
	for v in ttt:
		if pre == v:
			cc+=1
		else:
			pre=v
			
	return cc
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def can_set(sorted_al,k,cc):
	a=sorted_al[0]
	aa=(k//(cc+1))*cc+(k%(cc+1))
	#pa((a,aa))
	if a <= aa:
		return True
	return False

def main():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	
	if al[0] <= (k+1)//2:
		return 0
	if al[0] == k:
		return k-1
	
	ng=1
	ok=k
	while ok -ng >1:
		mm=(ng+ok) //2
		#print(mm,can_set(al,k,mm))
		if can_set(al,k,mm):
			ok=mm
		else:
			ng=mm
	return ok-1
	
	

def main2():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	ttt=[0]*k
	p=0
	for i, v in enumerate(al):
		for _ in range(v):
			ttt[p]=i
			p+=2
			if p >= k:
				p=1
	
	cc=0
	pre=-1
	for v in ttt:
		if pre == v:
			cc+=1
		else:
			pre=v
			
	return cc
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def can_set(sorted_al,k,cc):
	a=sorted_al[0]
	aa=(k//(cc+1))*cc+(k%(cc+1))
	#pa((a,aa))
	if a <= aa:
		return True
	return False

def main():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	
	if al[0] <= (k+1)//2:
		return 0
	if al[0] == k:
		return k-1
	ng=0
	ok=k-1
	while ok -ng >1:
		mm=(ng+ok) //2
		#print(mm,can_set(al,k,mm))
		if can_set(al,k,mm):
			ok=mm
		else:
			ng=mm
	return ok-1
	
	

def main2():
	k, t = IN()
	al = list(IN())
	al.sort(reverse=True)
	ttt=[0]*k
	p=0
	for i, v in enumerate(al):
		for _ in range(v):
			ttt[p]=i
			p+=2
			if p >= k:
				p=1
	
	cc=0
	pre=-1
	for v in ttt:
		if pre == v:
			cc+=1
		else:
			pre=v
			
	return cc
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
print(max(0,max(a)-(k+1)//2) if t!=1 else k-1)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
print(max(0,max(a)-(k+1)//2))

Submission status: Wrong Answer

Solution code:
# K個のケーキ
k,t=map(int,input().split())
a=list(map(int,input().split()))

if t==1:
    print(k-t)
    exit()
a.sort()
l=[]
nokori=0

for i in range(t):
    if i==t-1:
        nokori=a[i]
        break
    tmp=a[i]
    l.append(tmp)
    for j in range(t):
        a[j]-=tmp
# print(a)
# print(l)

ans=[1]*l[-1]
ans+=[0]*(sum(l)-l[-1]+1)
ans.sort()
# print(ans)
for i in range(nokori):
    i=i%len(ans)
    ans[i]+=1
# print(ans)
print(max(ans)-1)

Submission status: Wrong Answer

Solution code:
import math

K, T = map(int, input().split())
A = list(map(int, input().split()))

A.sort()
summation = sum(A[:-1])
maximum = A[-1]

#print(f'{maximum=} {summation=}')
if summation > maximum-2:
    print(0)
else:
    if summation != 0:
        ans = math.ceil(maximum/(summation+1))
        print('{}'.format(ans-1))
    else:
        print('{}'.format(maximum-1))

Submission status: Wrong Answer

Solution code:
k,t = map(int, input().split())
a = list(map(int, input().split()))
print(max(a) - t)

Submission status: Wrong Answer

Solution code:
K, T = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort(reverse=True)
if T > 1:
    n = a[0]-a[1]
else:
    print(a[0]-1)
    exit()
for i in range(2, T):
    n = abs(n-a[i])
print(n-1)

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())

print(max(list(map(int, input().split()))) - t)

Submission status: Wrong Answer

Solution code:
k, t = list(map(int, input().split()))
a = list(map(int, input().split()))
m = max(a)
n = k-m+1
print(max(int((m+n-1)/n)-1, 0))

Submission status: Wrong Answer

Solution code:
K,T = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=1)
if a[0] <= (K+1)//2:
    print(0)
else:
    if T == 1:
        print(a[0]-1)
    else:
        print(2*a[0] - K)

Submission status: Wrong Answer

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

A = list(map(int, input().split()))
m = max(A)

print(max(0, m - 1 - (T - m)))

Submission status: Wrong Answer

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

A = list(map(int, input().split()))
m = max(A)

print(max(0, m - 1 - (T - 1)))

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))

b = a.pop()
print(abs(b-sum(a))-1)

Submission status: Wrong Answer

Solution code:
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))

x = 0
y = 0
for i in a[::-1]:
    if x <= y:
        x += i
    else:
        y += i

print(abs(x-y)-1)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
# 個数が大きい順に並べて、答えの配列に偶数番目すべて、奇数番目すべての順で入れていく。
# ただし2周目は後ろから
cakes=[None]*t
for i in range(len(a)):
  cakes[i]=[a[i],i] # ケーキの数、ケーキの番号
cakes=sorted(cakes,key=lambda x:x[0])[::-1]

days=[0]*k
ci=0
for i in range(0,len(days),2):
  while cakes[ci][0]==0:
    ci+=1
  cakes[ci][0]-=1
  days[i]=cakes[ci][1]

ind=k-1
if k&1:
  ind-=1
  
for i in range(ind,-1,-2):
  while cakes[ci][0]==0:
    ci+=1
  cakes[ci][0]-=1
  days[i]=cakes[ci][1]

ans=0
for i in range(1,len(days)):
  ans+=(days[i]==days[i-1])
  
print(ans)

Submission status: Wrong Answer

Solution code:
k, t = map(int,input().split())
a = tuple(map(int,input().split()))

a0 = sorted(a)[::-1]

rem = a[0]
for i in range(len(a0)-1):
    rem = abs(rem-a[i+1]-1)

print(rem if t > 1 else k-1)

Submission status: Wrong Answer

Solution code:
k, t = map(int,input().split())
a = tuple(map(int,input().split()))

a0 = sorted(a)[::-1]

rem = a[0]
for i in range(len(a0)-1):
    rem = abs(rem-a[i+1])

print(rem-1 if t > 1 else k-1)

Submission status: Wrong Answer

Solution code:
import heapq
import bisect

k,t=map(int,input().split())
a=sorted([-int(i) for i in input().split()],reverse=True)

heapq.heapify(a)
while len(a)>=2:
 max=heapq.heappop(a)
 min=a.pop(-1)
 bisect.insort(a,max+1)
 if min+1<=-1:
  heapq.heappush(a,min+1)
if a[0]!=0:
 print(abs(a[0]+1))
else:
 print(0)

Submission status: Wrong Answer

Solution code:
import heapq
import bisect

k,t=map(int,input().split())
a=sorted([-int(i) for i in input().split()],reverse=True)

heapq.heapify(a)
while len(a)>=2:
 max=heapq.heappop(a)
 min=a.pop(-1)
 bisect.insort(a,max+1)
 if min+1<=-1:
  heapq.heappush(a,min+1)

if a:
 print(abs(a[0]+1))
else:
 print(0)

Submission status: Wrong Answer

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

print(max(0, (max(a) - (K // 2)) * 2 - (1 - K % 2)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
k, t = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)
if t == 1:
    print(A[0] - 1)
else:
    a = A[0]
    b = sum(A[1:])
    print(a-b-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
k, t = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)
if t == 1:
    print(A[0] - 1)
else:
    a = A[0]
    b = sum(A[1:])
    print(-(-a // (b+1)) - 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
k, t = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)
if t == 1:
    print(A[0] - 1)
else:
    a = A[0]
    b = sum(A[1:])
    print(-(-a // b) - 1)

Submission status: Wrong Answer

Solution code:
N,T = map(int,input().split())
A = list(map(int,input().split()))
print(max(A)-T)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
a = list(map(int,input().split()))
sm = sum(a)
mx = max(a)
print(max(0,(mx-(sm+1)//2)*2))

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
a = list(map(int,input().split()))
sm = sum(a)
mx = max(a)
print(max(0,mx-(sm+1)//2))

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    ans = "No"
    flag = False
    for s in S:
        if flag:
            if s=="F":
                ans = "Yes"
                break
        else:
            if s=="C":
                flag = True
    print(ans)
    return

def examB():
    K, T = LI()
    A = LI(); A.sort()
    ans = max(0,A[-1]*2-sum(A)-1)
    if len(A)==1:
        ans = A[0]
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Submission status: Wrong Answer

Solution code:
K, T, *a = map(int, open(0).read().split())
a = sorted(a)
for i in range(T-1):
  a[i+1] += a[i]
ans = K - 1
for i in range(T-1):
  ans = min(ans, abs(a[T-1] - 2 * a[i]) - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
K, T = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

buf = A[0]
i = 1
while i < T:
    sum_i = 0
    while i < T and sum_i < buf:
        sum_i += A[i]
        i += 1

    if buf > sum_i:
        print(buf - sum_i - 1)
        exit()
    else:
        buf = sum_i - buf
        i += 1

print(buf - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
K, T = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

buf = A[0]
i = 1
while i < T:
    sum_i = A[i]
    while i < T and sum_i < buf:
        sum_i += A[i]
        i += 1

    if buf > sum_i:
        print(buf - sum_i)
        exit()
    else:
        buf = sum_i - buf
        i += 1

print(buf - 1)

Submission status: Wrong Answer

Solution code:
k,t=map(int,input().split())
A=sorted(list(map(int,input().split())), key=lambda x: -x)
while len(A)!=1:
    A[0] -=A.pop(1)
    A=sorted(A, key=lambda x: -x)
print(A[0]-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
K,T=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

A.sort()
print max( 0, (A[-1]-1)-sum(A[:-2]) )

Submission status: Wrong Answer

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

print(max(A) - (K-max(A)+1))

Submission status: Wrong Answer

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

if T == 1:
    print(K)
    exit()
print(max(0, max(A) - (K-max(A)+1)))

Submission status: Wrong Answer

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

for i in range(K):
    if K - max(A) == i:
        print(max(A) // (i + 1) - 1 if max(A) % (i + 1) == 0 else max(A) // (i + 1))
        break