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:
import sys
input = sys.stdin.readline


def main():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    cakes = []
    for i, a in enumerate(A):
        cakes.append([i, a])

    pre = -1
    ans = 0
    for j in range(K):
        cakes.sort(key=lambda x: x[1], reverse=True)
        found = False
        for i in range(T):
            if cakes[i][0] != pre and cakes[i][1] > 0:
                pre = cakes[i][0]
                cakes[i][1] -= 1
                found = True
                break
        if not found:
            pre = cakes[0][0]
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    cakes = []
    for i, a in enumerate(A):
        cakes.append([i, a])

    order = [-1]*K
    pre = -1
    for j in range(K):
        uniq = False
        cakes.sort(key=lambda x: x[1], reverse=True)
        for i in range(T):
            if cakes[i][0] != pre and cakes[i][1] > 0:
                pre = order[j] = cakes[i][0]
                cakes[i][1] -= 1
                uniq = True
                break
        if not uniq:
            pre = order[j] = cakes[0][0]

    pre = -1
    tmp = 0
    ans = 0
#    print(order)
    for i in order:
        if i == pre:
            tmp += 1
            ans = max(ans, tmp)
        else:
            pre = i
            tmp = 0
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def cake(k, t, a):
    if t == 1:
        return k - 1

    a.sort()
    left = 0
    right = sum(a)
    diff = right

    for i in a:
        left += i
        right -= i
        diff = min(diff, abs(right-left))

    return max(0, diff-1)


if __name__ == "__main__":
    k, t = map(int, input().split())
    a = list(map(int, input().split()))
    ans = cake(k, t, a)
    print(ans)

Submission status: Accepted

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 = max(0, min(ans, abs(a[T-1] - 2 * a[i]) - 1))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    k, t = list(map(int, input().strip().split()))
    v = list(map(int, input().strip().split()))
    v.sort(reverse=True)
    if len(v) > 1:
        print(v[0]-1 - min(v[0]-1, sum(v[1:])))
    else:
        print(v[0]-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

L=[[i for i in range(2)]for j in range(T)]
for i in range(T):
    L[i][0]=i
    L[i][1]=N[i]

f=-1
c=0
for K in range(K):    
    L1=sorted(L,key=lambda x:x[1])
    if(f!=L1[-1][0]):
        f=L1[-1][0]
        L1[-1][1]-=1
    elif(L1[T-2][1]>0 and L1[T-2][0]!=f):
        f=L1[T-2][0]
        L1[T-2][1]-=1     
    else:
        c+=1
        f=L1[-1][0]
        L1[-1][1]-=1       
print(c)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

K, T, *a = map(int, read().split())
A = max(a)
if K // 2 >= A:
    print(0)
else:
    print(A * 2 - K - 1)

Submission status: Accepted

Solution code:
import numpy as np

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

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

if max(A) > K//2:
    print(2*max(A)-K-1)
else:
    print(0)

Submission status: Accepted

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

mx = max(a)
sm = sum(a)

print(max(mx-(sm-mx)-1,0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
p=max(a)
q=sum(a)
import math
if p<=math.ceil(q/2):
	print(0)
else:
	if k%2==0:
		t=-1
	else:
		t=0
	print(2*(p-math.ceil(q/2))+t)

Submission status: Accepted

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

m=max(a)

if K%2==0:
    if m<=K//2:
        ans=0
    elif m==K//2+1:
        ans=1
    else:
        ans=1+2*(m-1-K//2)
else:
    if m<=(K+1)//2:
        ans=0
    else:
        ans=2*(m-(K+1)//2)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

max_A = A[-1]
sum_A = sum(A[0:-1])

ans = max(max_A - (sum_A+1), 0)
print(ans)

Submission status: Accepted

Solution code:
#  k個t種類のケーキがある。
k,t = map(int,input().split())
# それぞれのケーキの個数リスト a
a = list(map(int,input().split()))
#print(k,t,a)

#タイプiのケーキ以外のケーキが何個あるのか調べる。
for i in range(t):
  not_i = k - 2 * a[i]
  #not_iがマイナスってことは、他のケーキの種類が足りていない。
  #逆にそれ以外のタイプのケーキにとっては、タイプiの方が多いんやから。足りてる。
  if not_i < 0:
    #一番最初の日に一番多いタイプを食べれば、１減らせる
    print(abs(not_i)-1)
    exit()
#前日と同じ奴じゃなくて済むやつしかなければ、0を出力    
print(0)

Submission status: Accepted

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 if A[0]!=0 else 0)

Submission status: Accepted

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

Submission status: Accepted

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[:-1]) )

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
l=list(map(int,input().split()))
m=0
for i in range(t):
  if m<l[i]:
    m=l[i]
n=k-m
if m>n+1:
  print(m-1-n)
else:
  print(0)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
d = [[i, c] for i, c in enumerate(A)]

if len(d) == 1:
    print(K-1)
    exit()

s = ''
ans = 0
pre = None
for i in range(K):
    d = sorted(d, key=lambda x: -x[1])
    if pre == d[0][0]:
        if pre != d[1][0] and d[1][1] > 0:
            d[1][1] -= 1
            pre = d[1][0]
            s += str(pre)
        else:
            d[0][1] -= 1
            pre = d[0][0]
            s += str(pre)
            ans += 1
    else:
        d[0][1] -= 1
        pre = d[0][0]
        s += str(pre)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
half_K = (K + 1) // 2
if A_max <= half_K:
  print(ans)
  quit()
else:
  A_ex = K - A_max + 1#A_ex個に一番多いやつを分けることができる。
  K_syo = A_max // A_ex
  K_amari = A_max % A_ex
  ans += (K_syo) * K_amari
  ans += (K_syo - 1) * (A_ex - K_amari)
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    k, t = map(int, input().split())
    a = list(map(int, input().split()))
    if t == 1:
        print(a[0] - 1)
    else:
        maxa = max(a)
        hoka = sum(a) - maxa
        if maxa <= hoka:
            print(0)
        else:
            print(maxa - hoka - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

if T==1:
  print(A[0]-1)
  exit()
  
ans=abs(A[0]-A[1])-1
k=A[0]+A[1]
for i in range(2,T):
  if ans>=A[i]:
    ans-=A[i]
  else:
    ans=max(A[i]-k-1,0)
  k+=A[i]  

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

if T == 1:
  print(A[0]-1)
else:
  A.sort()
  print(max(A[-1]-1-sum(A[:T-1]),0))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = [[int(x), i] for i, x in enumerate(input().split())]
pc = -1
while(True):
    a.sort(reverse=True)
    for i in range(t):
        if a[i][0] > 0 and a[i][1] != pc:
            a[i][0] -= 1
            pc = a[i][1]
            break
    else: break
print(sum([x for x, _ in a]))

Submission status: Accepted

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

print(max(ma-(sa-ma)-1,0))

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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


def argmax(except_i=None):
    m = 0
    ret = -1
    for i, a in enumerate(A):
        if a > m and i != except_i:
            ret = i
            m = a
    return ret


prev = argmax()
A[prev] -= 1

ans = 0
for _ in range(K - 1):
    i = argmax(prev)
    if i < 0:
        ans += 1
        A[prev] -= 1
    else:
        A[i] -= 1
        prev = i
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import heapq
K,T = [int(x) for x in stdin.readline().rstrip().split()]
data = [(-int(b),a) for a,b in enumerate(stdin.readline().rstrip().split())]
heapq.heapify(data)
ans = 0
cake_num = -1
cake_count = 0
flag = True
 
if T == 1:
  ans = K-1
else:
  while flag:
    c_c,c_n = heapq.heappop(data)
    if c_n == cake_num:
        c_c2,c_n2 = heapq.heappop(data)
        if c_c2 == 0:
            ans = abs(c_c)
            flag = False
        else:
            heapq.heappush(data,(c_c2+1,c_n2))
        cake_num = c_n2
        heapq.heappush(data,(c_c,c_n))
        #flag = False
    else:
        heapq.heappush(data,(c_c+1,c_n))
        cake_num = c_n
    if c_c == 0:
      ans = 0
      flag = False
    
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
#import heapq
K,T = [int(x) for x in stdin.readline().rstrip().split()]
data = [(int(b),a) for a,b in enumerate(stdin.readline().rstrip().split())]
#heapq.heapify(data)
ans = 0
cake_num = -1
flag = True
 
if T == 1:
    ans = K-1
else:
    while flag:
        data.sort()
        #print(data)
        c_c,c_n = data.pop()
        #print(c_c,c_n)
        if c_n == cake_num:
            c_c2,c_n2 = data.pop()
            if c_c2 == 0:
                ans = c_c
                flag = False
            else:
                data.append((c_c2-1,c_n2))
            data.append((c_c,c_n))
            cake_num = c_n2
            #flag = False
        else:
            data.append((c_c-1,c_n))
            cake_num = c_n
        if c_c == 0:
            ans = 0
            flag = False
        
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
a_max = max(a)
x = a_max - (a_sum - a_max) - 1
print(x if x > 0 else 0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

K, T = map(int, input().split())
A = [-a for a in map(int, input().split())]

heapify(A)
while len(A) > 1:
    a, b = -heappop(A), -heappop(A)
    heappush(A, -(a - b))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
if k >= a[0]*2:
    print(0)
else:
    print(a[0]*2-k-1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
K,T=map(int,input().split())
A=list(map(int,input().split()))

all=sum(A)
high=max(A)

print(max(0,high-(all-high)-1))

Submission status: Accepted

Solution code:
K, T = map(int,input().split())
List = [int(i) for i in list(input().split())]
List.sort(reverse = True)

Answer = max(List[0]-1-(K-List[0]), 0)

print(Answer)

Submission status: Accepted

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

Submission status: Accepted

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

if k%2==0:
    if 0<=2*(b-k//2)-1:
        print(2*(b-k//2)-1)
    else:
        print(0)

else:
    if 0<=2*(b-(k+1)//2):
        print(2*(b-(k+1)//2))
    else:
        print(0)

Submission status: Accepted

Solution code:
k, t, *a = list(map(int, open(0).read().split()))

最大 = max(a)
print(max(最大-(k-最大)-1, 0))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

k,n = inpl()
a = inpl()
a.sort()
print(max(0, a[-1]*2 - k - 1))

Submission status: Accepted

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

temp = []
temp.append(a.pop())
temp[-1] -= 1

while sum(a) != 0:
    a = sorted(a)
    temp.append(a.pop())
    temp[-1] -= 1
    a.append(temp.pop(0))

print(temp[0])

Submission status: Accepted

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

mode = max(a)

ans = max(0, (k-1) - (k-mode)*2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
#%%
A.sort(reverse=True)

print(max(A[0]-1-(K-A[0]),0))

Submission status: Accepted

Solution code:
import heapq

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

q = []
for i in range(t):
    heapq.heappush(q, (a[i] * -1, i))

cakes = [-1]
for _ in range(k):
    count1, cake1 = heapq.heappop(q)
    if cakes[-1] == cake1 and len(q) > 0:
        count2, cake2 = heapq.heappop(q)
        cakes.append(cake2)

        heapq.heappush(q, (count1, cake1))
        if count2 + 1 < 0:
            heapq.heappush(q, (count2 + 1, cake2))
    else:
        cakes.append(cake1)
        if count1 + 1 < 0:
            heapq.heappush(q, (count1 + 1, cake1))

ans = sum(1 for i in range(len(cakes) - 1) if cakes[i] == cakes[i + 1])
print(ans)

Submission status: Accepted

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

if max(A)-(sum(A)-max(A))<=1:
  print(0)
else:
  print(max(A)-(sum(A)-max(A))-1)

Submission status: Accepted

Solution code:
# coding: utf-8

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

if len(A) == 1:
    print(A[0] - 1)
else:
    A.sort()
    max_num = A.pop()
    tmp = max_num - sum(A)
    if tmp > 1:
        print(tmp - 1)
    else:
        print(0)

Submission status: Accepted

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

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

print(max(ans, 0))

Submission status: Accepted

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

Submission status: Accepted

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

temp=sum(a)-max(a)
print(max(max(a)-temp-1,0))

Submission status: Accepted

Solution code:
def main():

    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse = True)
    if K % 2 == 1 and A[0] > (K+1)//2:
        return (A[0] - (K+1)//2) * 2
    elif K % 2 == 0 and A[0] > K  // 2:
        if A[0] - K // 2 == 1:
            return 1
        else:
            return 1 + (A[0] - K // 2 - 1) * 2
    else:
        return 0

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    k, t = map(int, input().split())
    data = list(map(int, input().split()))
    ans = 0
    ikeru = (k + 1) // 2
    for i in range(t):
        if data[i] > ikeru:
            if k % 2:
                ans += (data[i] - ikeru) * 2
            else:
                ans += (data[i] - ikeru) * 2 - 1
    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k, t = [ int(v) for v in input().split() ]
cake_list = [ int(v) for v in input().split() ]

a = max(cake_list)
print(max(0,2*a-k-1))

Submission status: Accepted

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


def main():
    k, t = map(int, input().split())
    a = list(map(int, input().split()))
    max_value = 0
    max_value_index = -1
    ans = 0

    for index, ai in enumerate(a):
        if ai > max_value:
            max_value = ai
            max_value_index = index

    prev = max_value_index
    a[prev] -= 1

    # KeyInsight
    # できる限り前と同じケーキを選ばないようにしながら，残りが最も多いケーキを選択
    # See:
    # http://competitive-kivantium.hateblo.jp/entry/2016/10/24/135521
    for i in range(k - 1):
        max_value = 0
        max_value_index = -1

        # 残りのケーキが最大となるものを求める
        for j in range(t):
            if a[j] > max_value and j != prev:
                max_value = a[j]
                max_value_index = j

        if max_value_index != -1:
            prev = max_value_index
            a[max_value_index] -= 1
        else:
            a[prev] -= 1
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K,T,*A=map(int,open(0).read().split());print(max(0,(max(A)+-K//2)*2-(K+1)%2))

Submission status: Accepted

Solution code:
K,T,*A=map(int,open(0).read().split())
if K%2:print(max(0,(max(A)+-K//2)*2))
else:print(max(0,(max(A)+-K//2)*2-1))

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=[int(i) for i in input().split()]

a=sorted(a,reverse=True)

if len(a)==1:
	ans=a[0]-1

else:
	while True:
		if a[1]==0:
			ans=max(a[0]-1,0)
			break
		a[0]-=1
		a[1]-=1
		a=sorted(a,reverse=True)
print(ans)

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
if T == 1:
  print(K-T)
else:
  m = max(a)
  M = K-m+1
  if M >= m:
    print(0)
  else:
    print(m-M)

Submission status: Accepted

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

while(len(a)>0):
    a[-1]-=1
    if len(a)>1:
        a[-2]-=1
    else:
        count=a[0]
        break
    a=sorted([i for i in a if i>0])
print(count)

Submission status: Accepted

Solution code:
import math
K, T = map(int, input().split())
a = [int(i) for i in input().split()]
d = max(a) - math.ceil(K/2)
print(max(0,(d-1)*2+1))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = sorted([int(i) for i in input().split()])
print(0) if a[-1]-1 < sum(a[:-1]) 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()))

a = sorted(a,reverse = True)
ans = a.pop(0) - sum(a) - 1
if ans >= 0:
    print(ans)
else:
    print(0)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,t = LI()
a = LI()
maxa = max(a)
ans = max(maxa-1-(sum(a)-maxa),0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

max_ = max(a)
sum_nokori = sum(a) - max(a)
print(max(max_ - sum_nokori - 1, 0))

Submission status: Accepted

Solution code:
k,_,*a=map(int,open(0).read().split());print(max(0,2*max(a)+~k))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# code-festival-2016-qualcB - K個のケーキ / K Cakes
def main():
    # sandwich A[:-1] with A[-1]
    K, T = tuple(map(int, input().split()))
    A = sorted(map(int, input().split()))
    ans = max(0, A[-1] - 1 - sum(A[:-1]))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(k, t ,a):
    if t == 1:
        return k-1
    Q = [[i, num] for i, num in enumerate(a)]
    prev = -1
    ans = 0
    for i in range(k):
        Q = sorted(Q, key=lambda _:-_[1])
        i1, num1 = Q[0]
        i2, num2 = Q[1]
        if (prev != i1) or (num2 == 0):
            Q[0][1] -= 1
            if prev == i1:
                ans += 1
            prev = i1
        else:
            Q[1][1] -= 1
            prev = i2
    return ans

k, t = map(int, input().split())
a = list(map(int, input().split()))
print(solve(k, t, a))

Submission status: Accepted

Solution code:
k,t=map(int,input().split());a=list(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, 2 * max(a) - sum(a) - 1))

Submission status: Accepted

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

pre = -1
ans = 0
for i in range(k):
    m = 0
    mi = 0
    for j in range(t):
        if m < a[j] and j != pre:
            m = a[j]
            mi = j
    if m == 0:
        a[pre] -= 1
        ans += 1
    else:
        a[mi] -= 1
        pre = mi
print(ans)

Submission status: Accepted

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

max_a=max(a)
print(max(max_a-(k-max_a)-1,0))

Submission status: Accepted

Solution code:
# 2019/07/17

from heapq import heappop,heappush

k,t=map(int,input().split())
a=list(map(int,input().split()))
que=[]
for i in range(t):
    hq=(-a[i],i)
    heappush(que,hq)

pre_v,pre_idx=heappop(que)
hq=(pre_v+1,pre_idx)
heappush(que,hq)

cnt=0

for i in range(k-1):
    v,idx=heappop(que)
    if idx==pre_idx :
        if que:
            hq=(v,idx)
            v,idx=heappop(que)
            heappush(que,hq)    
        else:
            cnt+=-v
            break
    v+=1
    hq=(v,idx)
    pre_v,pre_idx=hq
    if v==0:continue
    heappush(que,hq)

print(cnt)

Submission status: Accepted

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

max_a = max(A)
sum_a = sum(A)
print(max(max_a - (sum_a-max_a) -1, 0))

Submission status: Accepted

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

Submission status: Accepted

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

b = max(a)

c = k-b


print(max(k-2*c-1,0))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

print(max(0,a[0]-sum(a[1:])-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:
def main():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    mx = max(A)
    if K % 2 == 0:
        ans = max((mx - K//2) * 2 - 1, 0)
    else:
        ans = max((mx - K//2 - 1) * 2, 0)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


def main():
    k, t = [int(e) for e in input().split()]
    aTop = max([int(e) for e in input().split()])
    print(max(0, (aTop * 2) - k - 1))


main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

if T == 1:
    print(K-1)
    exit()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = [int(x) for x in input().split()]
x = max(A)
other = K - x

answer = max(0, x - other - 1)
print(answer)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

K, T = inpl()
A = inpl()
ans = K

if T == 1:
    print(K-1)
    exit()

for i in range(T):
    tmp = max(A[i]-(K-A[i]+1), 0)
    OK = False
    for k in range(T):
        if i == k:
            continue
        if (K-A[k]-1) <= 0:
            continue
        OK = True
        tmp = max(tmp, A[k]-(K-A[k]-1))
    if OK:
        ans = min(tmp, ans)

for i in range(T):
    for j in range(i+1, T):
        tmp = max(A[i]-(K-A[i]), 0)
        tmp = max(tmp, A[j]-(K-A[j]))
        OK = False
        for k in range(T):
            if (i == k) or (j == k):
                continue
            if (K-A[k]-1) <= 0:
                continue
            OK = True
            tmp = max(tmp, A[k]-(K-A[k]-1))
        if OK:
            ans = min(tmp, ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

n = max(A)

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