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: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
B - K個のケーキ / K Cakes
https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b

"""
import sys


def solve(K, T, cakes):
    if T == 1:
        return K-1
    m = (K + 1)//2
    return max(cakes[-1]-m, 0, cakes[-1]-(K-cakes[-1])-1)


def main(args):
    K, T = map(int, input().split())
    cakes = sorted([int(a) for a in input().split()])
    ans = solve(K, T, cakes)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

print(max(0, max(a)*2 - sum(a) - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T = [int(i) for i in input().split()]
li = [int(i) for i in input().split()]

max_cake = max(li)
without_cake = sum(li) - max_cake

if (max_cake - without_cake - 1 < 0) :
    print(0)
else :
    print(max_cake - without_cake - 1)

Submission status: Accepted

Solution code:
k,f =map(int,input().split())
a = list(map(int,input().split()))
a.append(0)
a.sort()
t = a[-1]
s = sum(a[:-1])
if 1 == f:
    print(t-1)
elif t<=s:
    print(0)
else:
    print(t-s-1)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
A=[int(i) for i in input().split()]
m=max(A)
print(max(m-1-(k-m),0))

Submission status: Accepted

Solution code:
K,T=map(int,input().split());print(max(2*max(map(int,input().split()))-K-1,0))

Submission status: Accepted

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

mx = max(A)
print(max(2 * mx- K -1 ,0))

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
*A,=map(int,input().split())
m=max(A)
print(max(0,m-(K-m+1)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
A=list(map(int,input().split()))
from heapq import heappush,heappop
from collections import deque

A.sort(reverse=True)
d=deque(A)
d2=deque(A)
ans=A[0]
mod=1
while d:
  if len(d)==1:
    print(d[0]-1)
    exit()
  a=d.pop()
  b=d.popleft()
  if not a==1:
    d.append(a-1)
  if not b==1:
    d.appendleft(b-1)
print(0)

Submission status: Accepted

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

if (sum(a)-max(a))+1>=max(a):
    print(0)
else:
    print(max(a)-(sum(a)-max(a)+1))

Submission status: Accepted

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

ans = max(max(A) - sum(A[:-1]) -1 ,0)
print(ans)

Submission status: Accepted

Solution code:
k,t,*a=map(int,open(0).read().split());print(max(max(a)*2-sum(a),1)-1)

Submission status: Accepted

Solution code:
k,t,*a=map(int,open(0).read().split());print(max([i+i-k-1for i in a]+[0]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
print(max(0,max(list(map(int,input().split())))*2-n-1))

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
l=[int(i) for i in input().split()]
if t==1:
    print(l[0]-1)
    exit()
while 1:
    l.sort(reverse=True)
    if l[1]==0: break
    l[0]-=l[1]
    l[1]=0

print(max(0,l[0]-1))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
maximum=max(arr)
if (maximum-1)<=(sum(arr)-maximum):
  print(0)
else:
  print((maximum-1)-(sum(arr)-maximum))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K, T = [int(x) for x in input().split()]
a_s = [int(x) for x in input().split()]

a_max = max(a_s)
a_others = K - a_max
ans = max(0, a_max - a_others - 1)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush, heapify

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

K,T=MAP()
A=LIST()
A=[(-A[i], i) for i in range(T)]
heapify(A)

prev=-1
while len(A):
    v,i=heappop(A)
    if i!=prev:
        v+=1
        prev=i
        if v!=0:
            heappush(A, (v, i))
    else:
        if len(A)==0:
            print(-v)
            exit()
        v2,i2=heappop(A)
        v2+=1
        prev=i2
        if v2!=0:
            heappush(A, (v2, i2))
        heappush(A, (v, i))
print(0)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
l=list(map(int,input().split()))
if len(l)==1:
  print(k-1)
else:
  if k%2==0:
    print(max(0,(max(l)-k//2)*2-1))
  else:
    print(max(0,(max(l)-k//2-1)*2))

Submission status: Accepted

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

Submission status: Accepted

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

maxa = max(alist)
if k - maxa >= maxa:
  print(0)
else:
  print(maxa - (k - maxa) - 1)

Submission status: Accepted

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

a.sort()
print(a[T-1]-sum(a[:T-1])-1 if a[T-1]>sum(a[:T-1]) else 0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
l=list(map(int,input().split()))
sm=sum(l)
mx=max(l)
if mx-1<=sm-mx:
  print(0)
else:
  print(2*mx-1-sm)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = [int(_) for _ in input().split()]
maxcake = max(a)
print(max(0, 2*maxcake-K-1))

Submission status: Accepted

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

print(max(0,max(A)-(N-max(A))-1))

Submission status: Accepted

Solution code:
_ = input()
l = list(map(int,input().split()))
print(max(0, max(l)*2 - sum(l) - 1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T=map(int,input().split(' '))
A=sorted(list(map(int,input().split(' '))))[::-1]
print(max(0, A[0]-1-sum(A[1:])))

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
if A[len(A)-1] <= K//2:
  print(0)
else:
  print(A[len(A)-1]*2-K-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

k,t = li()
a = list(li())

ans = 0

for ai in a:
    if  k%2 == 1 and ai > k//2 + 1:
        ans = (ai - (k//2+1)) * 2
            
    elif k%2 == 0  and ai > k//2:
        ans = 1 + (ai - (k//2+1)) * 2
        
print(ans)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = [[int(m), 0] for m in input().split()]
prohibit = 1
ans = 0
if t == 1:
    ans = a[0][0] - 1
else:
    for i in range(k):
        a.sort(reverse=True)
        if a[1][0] == 0:
            ans = a[0][0] - 1
            break
        else:
            if i == 0:
                a[1][1] = 1
            if a[0][1] == 0:
                a[0][0] -= 1
                a[0][1] = 1
                prohibit = 0
            elif a[1][1] == 0:
                a[1][0] -= 1
                a[1][1] = 1
                prohibit = 1
            for j in range(t):
                if prohibit != j:
                    a[j][1] = 0
print(ans)

Submission status: Accepted

Solution code:
k,t,*a=map(int,open(0).read().split())
b=sorted(a)
try:
    c=b[-1]-sum(b[:-1])-1
    if c>0:
        print(c)
    else:
        print(0)
except:
    print(b[0]-1)

Submission status: Accepted

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

maxA = max(As)
sumA = sum(As)
print(max(0, maxA - (sumA - maxA) - 1))

Submission status: Accepted

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

mx = max(A)
if mx <= (K+1)//2:
    print(0)
    exit()

if K%2:
    print(2 *(mx - (K+1)//2))
else:
    print(2 * (mx - K//2) - 1)

Submission status: Accepted

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

mx = max(A)
if mx <= (K+1)//2:
    print(0)
    exit()

if K%2:
    print(2 *(mx - (K+1)//2))
else:
    print(2 * (mx - K//2) - 1)

Submission status: Accepted

Solution code:
k,t = (int(i) for i in input().split())
a = list(int(i) for i in input().split())
print(max(0,2*max(a)-sum(a)-1))

Submission status: Accepted

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

dom = max(A)
other = sum(A) - dom

if K%2 >0:
  print(max(0, (dom-(K+1)//2)*2))
else:
  print(max(0, (dom-K//2)*2 -1))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
k,t = map(int,input().split(' '))
cake = list(map(int,input().split(' ')))
sum = 0
maxCake = -1
for i in range(t):
    maxCake = max(maxCake,cake[i])
print(max(maxCake - 1 - (k - maxCake), 0))

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
d=list(map(int,input().split()))
d.sort()
print(max(0,2*d[-1]-sum(d)-1) if t!=1else k-1)

Submission status: Accepted

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

A = sorted(list(map(int,input().split())),reverse=True)
at = A[0]

ans = max(0,at - 1 - (K - at))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

a.sort()

ans=max(a[T-1]-sum(a[:-1])-1,0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

while a != [0] * (t-1) + [a[-1]]:
    a[-2], a[-1] = 0, a[-1] - a[-2]
    a = sorted(a)

print(a[-1]-1 if a[-1]>0 else 0)

Submission status: Accepted

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

print(max(0, 2*max(a)-sum(a)-1))

Submission status: Accepted

Solution code:
K, T = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
print(max(2 * max(A) - sum(A) - 1, 0))

Submission status: Accepted

Solution code:
import bisect
K, T = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
while len(A) > 1:
    A[-1] -= 1
    if A[-1] == 0:
        A = A[:-1]
    else:
        i_bisect_left = bisect.bisect_left(A[:-1], A[-1])
        if i_bisect_left == len(A) - 1:
            A = A[:-2] + [A[-1], A[-2]]
        else:
            v = A[-1]
            A = A[:-1]
            A.insert(i_bisect_left, v)
print(A[0] - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
if sum(A[:-1]) >= A[-1]-1 :
    ans = 0
else :
    ans = A[-1]-1 - sum(A[:-1])
print(ans)

Submission status: Accepted

Solution code:
K, T = map(int,input().split())
a = [int(i) for i in input().split()]
am = max(a)
if am-1 <= sum(a) - am:
    print(0)
else:
    print(2*am -1 -sum(a))

Submission status: Accepted

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

if T == 1:
	print(K - 1)
else:
	if 2 * a[-1] - K - 1 >= 0:
		print(2 * a[-1] - K - 1)
	else:
		print(0)

Submission status: Accepted

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

while a!=[a[0]]+[0]*(t-1):
    a = sorted(a,reverse=True)
    a[0],a[1] = a[0]-a[1],0

print(max(a[0]-1,0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k,t=map(int, input().split())
a=list(map(int, input().split()))
a.sort(reverse=True)
m=a[0]
a=a[1:]
print(max(m-1-sum(a),0))

Submission status: Accepted

Solution code:
k,t = map(int, input().split())
list_cake = list((map(int, input().split())))
list_cake.sort()
if list_cake[-1] <= k/2:
    print(0)
else:
    print(k - (k-list_cake[-1]) * 2 - 1)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if a[-1] - 1 <= sum(a[:-1]):
    print(0)
else:
    print(a[-1] - 1 - sum(a[:-1]))

Submission status: Accepted

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

if t == 1:
    print(k-1)
    exit()

ans = 0
before = -1
for i in range(k):
    A.sort(reverse=True)
    # print(A)
    if A[0] == before-1:
        if A[1] == 0:
            before = A[0]
            A[0] -= 1
            ans += 1
        else:
            before = A[1]
            A[1] -= 1
    else:
        before = A[0]
        A[0] -= 1
    before
print(ans)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
print(max(a[-1] - sum(a[:-1]) - 1, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

K,T = inpl()
aa = inpl()
MAX = max(aa)

if MAX <= (K+1)//2:
	print(0)
else:
	zan = MAX - (K+1)//2
	if K%2 == 0:
		print(zan*2-1)
	else:
		print(zan*2)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
while len(a) > 1:
    a.sort()
    a[0] -= 1
    a[-1] -= 1
    while 0 in a:
        a.remove(0)
if len(a) == 0:
    print(0)
else:
    print(a[0]-1)

Submission status: Accepted

Solution code:
k,t = list(map(int,input().split()))
a = list(map(int,input().split()))
p = max(a)
res = p-1 - (k-p)
if res >= 0:
    print(res)
else:
    print(0)

Submission status: Accepted

Solution code:
K,T=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
s=sum(a)
b=s-a[0]
if b>=a[0]-1:
  print 0
else:
  print a[0]-1 - b

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
a_s = sorted(a, reverse=True)
buf = 0
for i in range(t):
    buf = abs(buf - a_s[i])
print(buf - 1 if buf > 0 else 0)

Submission status: Accepted

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

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

answer=max(a)

print(max(0,answer-(K-answer+1)))
#K-answerで一番多いケーキを除いたケーキの個数が分かる。
#実際には◎×◎△◎のように1個分多く処理できるため、さらに1個分余分にmaxから引く

Submission status: Accepted

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

Submission status: Accepted

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

max_a = max(A)
print(max(max_a - 1 - (K - max_a), 0))

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
cakes = list(map(int,input().split()))
maxC=max(cakes)
if maxC - 1 <= (K-maxC):
  print(0)
else:
  print(K - (2*(K-maxC) + 1))

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
a=[int(i) for i in input().split()]
M=max(a)
print(max([2*M-1-K,0]))

Submission status: Accepted

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

A = sorted(list(map(int,input().split())),reverse=True)

BOSS_CAKE = A[0] - 1
for a in A[1:]:
    BOSS_CAKE -= a
    if BOSS_CAKE<=0:
        BOSS_CAKE = 0
        break

print(BOSS_CAKE)

Submission status: Accepted

Solution code:
k,t = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
if (k+1)//2>=max(a): print(0)
else: print(2*max(a)-(sum(a)+1))

Submission status: Accepted

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

Submission status: Accepted

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

print(max(max(a)*2-n-1,0))

Submission status: Accepted

Solution code:
import sys


k,t=map(int,input().split())
a=list(map(int,input().split()))
if(t==1):print(k-1)
else:
    eaten=-1
    ma=0
    s=sum(a)
    for i in range(s):
        nothing=1
        for j in range(len(a)):
            if(a[j]>ma and j!=eaten):
                ma=a[j]
                keep=j
                nothing=0
        
        if(nothing):
            print(max(a))
            sys.exit()
        else:
            eaten=keep
            a[eaten]-=1
            ma=0
    print(0)

Submission status: Accepted

Solution code:
def main():
    """
    一番多い数の種類のケーキから食べる
    上記と異なる種類のケーキのうち、一番多い数の種類のケーキを食べる
    以下繰り返し
        他のケーキの個数がすべて0なら連続日数として追加
    """
    K, T = map(int, input().split())
    A = map(int, input().split())

    A = list(A)
    f(K, T, A)


def f(K, T, A):
    cake_type = None
    rest_K = K
    ans = 0
    while rest_K > 0:
        bef_cake_type = cake_type
        max_a = 0
        for i, a in enumerate(A):
            if a > max_a and i != bef_cake_type:
                cake_type = i
                max_a = a

        A[cake_type] -= 1
        rest_K -= 1
        if bef_cake_type == cake_type:
            ans += 1
        #print(A, "cur:", cake_type, "bef:", bef_cake_type, sep="\t")

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
K, T = map(int, input().split())
a = list(map(int, input().split()))
s = 0
a.sort(reverse=True)
for i in range(1, T):
    s += a[i]

print(max(0, a[0] - s - 1))

Submission status: Accepted

Solution code:
K,T = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

num = (K - max(a))
if (max(a) - 1) > num:
    print((max(a) - 1) - num)
else:
    print(0)

Submission status: Accepted

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

A = list(map(lambda x: -int(x), input().split()))

import heapq as hq

hq.heapify(A)

a = hq.heappop(A)

while A:
  if a == -1:
    a = hq.heappop(A)
  else:
    a = hq.heapreplace(A,a+1)

print(-a-1)

Submission status: Accepted

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

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

sa = sorted(a)

print(max(0, sa[-1]-sum(sa[:-1])-1))

Submission status: Accepted

Solution code:
line = input().split()
K = int(line[0])
T = int(line[1])
a = map(int,input().split())
print(max(0,2*max(a)-1-K))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

if __name__ == "__main__":
    K,T = map(int, input().split())
    data = list(map(int, input().split()))
    cake = []
    for i,x in enumerate(data):
        cake.append([x, i])
    heapq._heapify_max(cake)
    while (len(cake) > 1):
        heapq._heapify_max(cake)
        p = heapq.heappop(cake)
        q = heapq.heappop(cake)
        # print (p,q)
        p[0] -= 1
        q[0] -= 1
        if p[0] > 0:
            heapq.heappush(cake, p)
        if q[0] > 0:
            heapq.heappush(cake, q)
    result = 0
    if len(cake) > 0:
        t = heapq.heappop(cake)
        result = t[0]
    print (max(0, result - 1))

Submission status: Accepted

Solution code:
k,t=map(int,raw_input().split())
a=max(map(int,raw_input().split()))
print max(0, a-(k-a)-1)

Submission status: Accepted

Solution code:
raw_input()
A=map(int,raw_input().split())
print~-max(2*max(A)-sum(A),1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8


K, T = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
m = max(a)
s = sum(a) - m
if m - s < 2:
    print(0)
else:
    print(m - s - 1)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = sorted(list(map(int, input().split())))
print(max(0, a[t-1]-sum(a[:t-1])-1))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = sorted(int(x) for x in input().split())
print(max(0, a[-1] - sum(a[:-1]) - 1))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
K, T = map(int, raw_input().split())
a = map(int, raw_input().split())
print max(max(a) - (sum(a) - max(a) + 1), 0)

Submission status: Accepted

Solution code:
ini=map(int, raw_input().split())
kind=map(int, raw_input().split())
kind.sort()
kind.reverse()
a=0
b=0
for i in range(ini[1]):
	if i==0:
		a=kind[0]-1
		b=2
	else:
		if a>=kind[i]:
			a-=kind[i]
			if a==kind[i]:
				b+=kind[i]*2-1
			else:
				b+=kind[i]*2
		else:
			kind[i]-=a
			b+=kind[i]
			a=0

print a

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# get two integers separated with half-width break
k, t = map(int, raw_input().split())
ls_a = map(int, raw_input().split())

print max(2 * max(ls_a) - 1 - sum(ls_a), 0)

Submission status: Accepted

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

pred = -1
ans = 0
a = [ (a[i],i) for i in range(T)]
while max(a)[0] > 0:
    a.sort()
    m,i = a[-1]
    flg = False
    for j in range(T-1,-1,-1):
        if pred != a[j][1] and a[j][0] > 0:
            a[j] = a[j][0]-1,a[j][1]
            pred = a[j][1]
            flg = True
            break
    if not flg:
        a[-1] = a[-1][0]-1,a[-1][1]
        ans += 1
        

print(ans)

Submission status: Accepted

Solution code:
import sys
i=1
t=True
nums=[]
for line in sys.stdin:
    if i%2==0:
        nums=line.split()
        index=0
        for number in nums:
        	nums[index]=int(nums[index])
        	index=index+1
        i=i+1
    else:
        i=i+1
        continue
    nums.sort()
    leng=len(nums)-1
    maxi=max(nums)
    maxnum=nums.count(maxi)
    if maxnum>=2:
        print(0)
    else:
        if leng>0:
            second=nums[0:leng]
            sum=0
            for number in second:
                sum=sum+int(number)
            diff=maxi-sum
            if diff<=1:
                print(0)
            else:
                print(diff-1)
        else:
            print(maxi-1)

Submission status: Accepted

Solution code:
k,t = [int(x) for x in raw_input().split()]
a = [int(x) for x in raw_input().split()]

a.sort()
res = a[-1] - sum(a[:-1])

if res<=1:
    print 0
else:
    print res-1

Submission status: Accepted

Solution code:
import sys

K,T = map(int, sys.stdin.readline().split())
a = map(int, sys.stdin.readline().split())

limit = K/2 + K%2
am= max(a)

if am > limit:
    print (am-1) - (K - am)                                                                                                                                                                                                           
else:
    print 0

Submission status: Accepted

Solution code:
def read():
	return [int(i) for i in input().split(" ")]
def maxInx(L, pre):
	tempM = [0, 0]
	for i in range(len(L)):
		if(L[i] > tempM[1] and i != pre):
			tempM = [i, L[i]] 
	return tempM[0] if tempM != [0, 0] else pre

(K, T) = read()
A = read()
pre = -1
sameDay = 0
for i in range(K):
	inx = maxInx(A, pre) 
	if(inx == pre):
		sameDay += 1
	A[inx] -= 1
	pre = inx
print(sameDay)

Submission status: Accepted

Solution code:
import sys
k,t=[int(i) for i in input().split()]
array=[int(i) for i in input().split()]
array.sort()
array=array[::-1]
max=array[0]
for i in range(1,len(array)):
    max-=array[i]
    if max<=0:
        print(0)
        sys.exit()
print(max-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import collections


def main():
    k, t = (int(x) for x in input().split())
    ctr = collections.Counter(dict(enumerate(int(a) for a in input().split())))
    pred = -1
    ans = 0
    sign = True
    for _ in range(k):
        if sign:
            mc = ctr.most_common()
        else:
            mc = ctr.most_common()[::-1]
        for k, v in mc:
            if k != pred and v > 0:
                pred = k
                ctr[k] = v - 1
                break
        else:
            ans += 1
            ctr[pred] -= 1
        sign = not sign
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
line = raw_input()
vals = map(int, line.split())
K = vals[0]
T = vals[1]
line = raw_input()
A = map(int, line.split())

def cal():
    A.sort()
    A.reverse()

    S = sum(A[1:])
    if S >= A[0] - 1:
        return 0

    return A[0] - 1 - S

print cal()

Submission status: Accepted

Solution code:
def chk_cake():
    for i in range(0, cake_kind):
        if cakes[i] > 0:
            return True
    return False


def get_max(last_cake):
    max_num = 0
    max_inx = last_cake
    for i in range(0, cake_kind):
        if max_num < cakes[i] and i != last_cake:
            max_num = cakes[i]
            max_inx = i
    return max_inx

counter = 0
cake_num, cake_kind = map(int, raw_input().split())
cakes = map(int, raw_input().split())

last_cake = -1
while chk_cake():
    i = get_max(last_cake)
    cakes[i] = cakes[i] - 1
    if i == last_cake:
        counter += 1
    last_cake = i

print counter

Submission status: Accepted

Solution code:
def f():
    line = list(map(int, input().split()))
    k = line[0]
    t = line[1]
    a = list(map(int, input().split()))
    a.sort()

    if t == 1:
        return k-1
    if t == 2:
        return a1-a0-1
    a = [0] + a
    n1 = a[-1] - a[-2]
    n2 = 1
    for i in range(1, t-1):
        n2 = n2 + (a[i]-a[i-1])*(t-i-1)
    if n1 < n2:
        return 0
    else:
        return n1 - n2

print (f())

Submission status: Accepted

Solution code:

def getMax(a, b):
    if a > b:
        return a
    return b

def getCakeRepeats(cakes):
    front_iter = 0
    back_iter = len(cakes) - 1

    while back_iter > front_iter:
        if cakes[back_iter] < cakes[front_iter]:
            cakes[front_iter] -= cakes[back_iter]
            cakes[back_iter] = 0
            back_iter -= 1
        elif cakes[back_iter] > cakes[front_iter]:
            cakes[back_iter] -= cakes[front_iter]
            cakes[front_iter] = 0
            front_iter += 1
        else:
            cakes[back_iter] = 0
            cakes[front_iter] = 0
            back_iter -= 1
            front_iter += 1

    return getMax(0, sum(cakes) - 1)

if __name__ == "__main__":
    setup = raw_input()
    cakes = list(map(int, raw_input().split()))
    print getCakeRepeats(sorted(cakes))

Submission status: Accepted

Solution code:
[K, T] = map(int, raw_input().split(' '))
cakes = map(int, raw_input().split(' '))

print max(0, 2 * max(cakes) - sum(cakes) - 1)

Submission status: Accepted

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

list.sort()
if T > 1:
        p = list[-1] - list[-2]

        sum = 0
        for k in list[:-2]:
                sum += k

        if p - sum <= 1:
                print(0)
        else:
                print(p - sum - 1)
else:
        print(K-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import copy
K,T=map(int,raw_input().split())
arr=map(int,raw_input().split())

yesterday=-1
nokori1=False
for i in range(K):
    
    mai=arr.index(max(arr))
    if yesterday!=mai:
        arr[mai]-=1     #一番多いのを食べる
        yesterday=mai
        #print mai
    else:
        for j in range(len(arr)+1):
            if j==len(arr):
                nokori1=True
                break
            if arr[j]>0 and yesterday!=j:
                arr[j]-=1
                yesterday=j
                #print j
                break
    if nokori1:
        break
ans=0
if arr.index(max(arr))==yesterday:
    ans=max(arr)
else:
    ans=max(arr)-1
if ans==-1:
    ans+=1
print ans