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:
def main():
    _ = input()
    a = sorted([int(n) for n in input().split()], reverse=True)
    c = 0

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

    while True:
        if a[1] == 0:
            print(a[0] - 1)
            return

        # if a[0] == 0:
        #     print(c)
        #     return

        a[0] -= 1
        a[1] -= 1
        a = sorted(a, reverse=True)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
import heapq
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

#n=int(raw_input())
n,k=map(int,raw_input().split())
l=[100-int(x) for x in raw_input().split()]
ans=chk=0
for i in range(n):
    if i%2==0:
        tmp=heapq.heappop(l)
        if tmp+1<100:
            heapq.heappush(l,tmp+1)
    else:
        tmp=heapq.heappop(l)
        tmp2=heapq.heappop(l)
        if tmp2+1<100:
            heapq.heappush(l,tmp2+1)
        heapq.heappush(l,tmp)
    if len(l)==1:
        print 100-l[0]
        exit()
print 0


#end = time.clock()
#print end - start

Submission status: Wrong Answer

Solution code:

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 sum(cakes) - 1

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

Submission status: Wrong Answer

Solution code:
s = input().split()

size = []
for n in s:
    size.append(int(n))

s2 = input().split()

ss = []
for n in s2:
    ss.append(int(n))

if size[0] % 2 == 0:
    k = size[0]/2
else:
    k = (size[0] + 1) /2

l = 0
m = 3

for i in ss:
    if i > k:
        l+=1
        while i > int((m-1) * (size[0] + ((m - (size[0] % m))%m)) / m) and m <= size[0]:
            m+=1
         
            l+=1

print (l)

Submission status: Wrong Answer

Solution code:
s = input().split()

size = []
for n in s:
    size.append(int(n))

s2 = input().split()

ss = []
for n in s2:
    ss.append(int(n))

if size[0] % 2 == 0:
    k = size[0]/2
else:
    k = (size[0] + 1) /2

l = 0
m = 3

for i in ss:
    if i > k:
        l+=1
        while i > int((m-1) * size[0] / m + size[0] % m) and m <= size[0]:
            m+=1
         
            l+=1

print (l)

Submission status: Wrong Answer

Solution code:
s = input().split()

size = []
for n in s:
    size.append(int(n))

s2 = input().split()

ss = []
for n in s2:
    ss.append(int(n))

if size[0] % 2 == 0:
    k = size[0]/2
else:
    k = (size[0] + 1) /2

l = 0
m = 3

for i in ss:
    if i > k:
        l+=1
        while i > int((m-1) * size[0] / m) and m <= size[0]:
            m+=1
         
            l+=1

print (l)

Submission status: Wrong Answer

Solution code:
k,_ = map(lambda x:int(x), raw_input().split())
s = map(lambda x:int(x), raw_input().split())

#u : cost
#i : eated
def recf(s, u, i):
    minu = k

    if sum(s) == 0:
        return u

    for x in range(len(s)):
        if s[x] <= 0:
            continue

        s_ = list(s)
        s_[x]  = s_[x] - 1
        ans = recf(s_, ((u + 1) if i == x else u), x) + u
        if ans < minu:
            minu = ans

    return minu

print recf(s, 0, -1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())
a = sorted(a,reverse=True)
# b = range(len(a))
# c = a[:]
# a = []
# for i in xrange(len(b)):
#     a.append([c[i], i])
# d = 0
# y = -1
# while True:
#     # print a
#     # print y
#     if len(a) == 1:
#         d += a[0][0]-1
#         break
#     else:
#         if a[0][0] == 0:
#             break
#         elif a[0][1] != y:
#             a[0] = [a[0][0]-1,a[0][1]]
#             y = a[0][1]
#         else:
#             if a[1][0] == 0:
#                 d += a[0][0]
#             a[1] = [a[1][0]-1,a[1][1]]
#             y = a[1][1]
#         a = sorted(a,reverse=True)
if t == 1:
    d = t-1
else:
    d = a[0] - sum(a[1:]) -1
    if d < 0:
        d = 0
print d

Submission status: Wrong Answer

Solution code:
l = input()
K, T = int(l.split()[0]), int(l.split()[1])
l = input()
ts = [int(x) for x in l.split()]
ts.sort(reverse=True)
print(K,T,ts)
if len(ts)==1:
	print (ts[0]-1)
else:
	d = ts[0] - (sum(ts[1:])+1)
	if d > 0:
		print(d)
	else:
		print(0)

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())
a = sorted(a,reverse=True)
b = range(len(a))
c = a[:]
a = []
for i in xrange(len(b)):
    a.append([c[i], i])
d = 0
y = -1
while True:
    # print a
    # print y
    if len(a) == 1:
        d += a[0][0]-1
        break
    else:
        if a[0][0] == 0:
            break
        elif a[0][1] != y:
            a[0] = [a[0][0]-1,a[0][1]]
            y = a[0][1]
        else:
            if a[1][0] == 0:
                d += a[0][0]-1
            a[1] = [a[1][0]-1,a[1][1]]
            y = a[1][1]
        a = sorted(a,reverse=True)

print d

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())
a = sorted(a,reverse=True)
b = range(len(a))
c = a[:]
a = []
for i in xrange(len(b)):
    a.append([c[i], i])
d = 0
y = -1
while True:
    # print a
    # print y
    if len(a) == 1:
        d += a[0][0]-1
        break
    else:
        if a[0][0] == 0:
            break
        elif a[0][1] != y:
            a[0] = [a[0][0]-1,a[0][1]]
            y = a[0][1]
        else:
            if a[1][0] == 0:
                d += a[0][0]
            a[1] = [a[1][0]-1,a[1][1]]
            y = a[1][1]
        a = sorted(a,reverse=True)

print d

Submission status: Wrong Answer

Solution code:
k,t=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
for i in xrange(t):
    j=t-1
    while 1:
        if i==j:
            print(a[i]-1)
            exit()
        if a[j]>=a[i]:
            a[j]-=a[i]
            break
        else:
            a[i]-=a[j]
            a[j]=0
            j-=1

Submission status: Wrong Answer

Solution code:
k, t = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a.sort()
a.reverse()
same_eaten = 0

a[0] -= 1
last_index = 0
k -= 1
for _ in range(k):
    eaten = False
    for i in range(len(a)):
        if i != last_index and a[i] > 0:
            eaten = True
            a[i] -= 1
            last_index = i
            a.sort()
            a.reverse()
            break
    if not eaten:
        same_eaten += 1
print(same_eaten)

Submission status: Wrong Answer

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


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

a = [0]*T
for i in range(T):
	a[i] = (hoge[i], i)




if T == 1:
	print(K-1)
else:
	a.sort()
	a[-1] = (a[-1][0] - 1, a[-1][1])
	pre = a[-1][1]

	for i in range(K-1):
		a.sort()
		if a[-1][0] == 0:
			print(0)
			break
		elif a[-1][1] != pre:
			a[-1] = (a[-1][0] - 1, a[-1][1])
			pre = a[-1][1]
		else:
			if a[-2][0] == 0:
				print(a[-1][1])
				break
			else:
				a[-2] = (a[-2][0] - 1, a[-2][1])
				pre = a[-2][1]

Submission status: Wrong Answer

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

while len(a) > 1:
    tmp = abs(a.pop() - a.pop())
    if tmp:
        a.append(tmp)

if not a:
    print 0
else:
    print a[0] - 1

Submission status: Wrong Answer

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

while len(a) > 1:
    tmp = abs(a.pop() - a.pop())
    if not tmp:
        a.append(tmp)

if not a:
    print 0
else:
    print a[0] - 1

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().split())
a = map(int, raw_input().split())
a = sorted(a,reverse=True)
b = range(len(a))
c = a[:]
a = []
for i in xrange(len(b)):
    a.append([c[i], i])
d = 0
y = -1
for c in xrange(k):
    # print a
    # print y
    if len(a) == 1:
        d += a[0][0]-1
        break
    else:
        if a[0][0] == 0:
            break
        elif a[0][1] != y:
            a[0] = [a[0][0]-1,a[0][1]]
            y = a[0][1]
        else:
            if a[1][0] == 0:
                d += a[0][0]
            a[1] = [a[1][0]-1,a[1][1]]
            y = a[1][1]
        a = sorted(a,reverse=True)

print d

Submission status: Wrong Answer

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


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

a = [0]*T
for i in range(T):
	a[i] = (hoge[i], i)




if T == 1:
	print(K-1)
else:
	a.sort()
	a[-1] = (a[-1][0] - 1, a[-1][1])
	pre = a[-1][1]

	for i in range(K-1):
		a.sort()
		if a[-1][0] == 0:
			print(0)
			break
		elif a[-1][1] != pre:
			a[-1] = (a[-1][0] - 1, a[-1][1])
		else:
			if a[-2][0] == 0:
				print(a[-1][1])
				break
			else:
				a[-2] = (a[-2][0] - 1, a[-2][1])
				pre = a[-2][1]

Submission status: Wrong Answer

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

while len(a) > 1:
    if a[0] > a[1]:
        a[0] -= a[1]
        a.pop(1)
    elif a[1] > a[0]:
        a[1] -= a[0]
        a.pop(0)
    else:
        a.pop(0)
        a.pop(1)

if not a:
    print 0
else:
    print a[0] - 1

Submission status: Wrong Answer

Solution code:
k,n = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 0
before = -1
m = n
for i in xrange(k):
    if m + 1 < n:
        newa = a[:m] + a[m+1:]
    else:
        newa = a[:m]
    if sum(newa) != 0:
        m = max(range(len(newa)), key=lambda i: a[i])
        if before <= m:
            m += 1
            
    a[m] -= 1
    if m == before:
        ans += 1
    before = m
    
print ans

Submission status: Wrong Answer

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

M = max(a)
print(max(0, 2*(M-(k//2+1))+1+k%2))

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())
ans = 0
for i in a:
    ans += min(i - 1, max(0, 2*(i - (k + 1) / 2)))
print ans

Submission status: Wrong Answer

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


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

a = [0]*T
for i in range(T):
	a[i] = (hoge[i], i)

a.sort()


if T == 1:
	print(K-1)
else:
	a[-1] = (a[-1][0] - 1, a[-1][1])
	pre = a[-1][1]

	for i in range(K-1):
		a.sort()
		if a[-1][0] == 0:
			print(0)
			break
		elif a[-1][1] != pre:
			a[-1] = (a[-1][0] - 1, a[-1][1])
		else:
			if a[-2][0] == 0:
				print(a[-1][1])
				break
			else:
				a[-2] = (a[-2][0] - 1, a[-2][1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

# def remax(seq):
#     m = max(seq)
#     for idx,i in enumerate(seq):
#         if m==i:
#             return (idx, m)
#
# lastK = -1
# cnt = 0
# for _k in range(K):
#     remax
#

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())
ans = 0
for i in a:
    ans += i - (k + 1) / 2
print ans

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
K, T = map(int, raw_input().split())
a = map(int, raw_input().split())
total = sum(a)
maxcake = max(a)
expectedmax = (total + 1) / 2
dupes = max(0, maxcake - expectedmax)
print dupes

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())
a.sort()
if len(a) == 1:
    print max(0, a[-1] - 1)
else:
    print max(0, a[-1] - a[-2] - 2)

Submission status: Wrong Answer

Solution code:
k, t = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())
a.sort()
if len(a) == 1:
    print a[-1] - 1
else:
    print a[-1] - a[-2] - 2

Submission status: Time Limit Exceeded

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
# print(a)
m = 10 ** 5
for situ in range(0, 2 ** T):
    block_a = 0
    block_b = 0
    for j in range(T):
        if (situ >> j) & 1:
            block_a += a[j]
        else:
            block_b += a[j]
    diff = abs(block_a - block_b)
    # print(bin(situ), block_a, block_b, diff)
    m = min(diff, m)
print(max(0, m - 1))

Submission status: Time Limit Exceeded

Solution code:
def read_input():
    l_1 = input()
    day = int(l_1.split(" ")[0])

    num_cake = [int(i) for i in input().split(" ")]

    return day, num_cake

def get_max_index(target_list):
    return [i for i, j in enumerate(target_list) if j == max(target_list)]


def get_second_max_index(target_list):
    return [i for i, j in enumerate(target_list) if j == list(sorted(set(target_list), reverse=True))[1]]


def mog(day, num_cake):
    """

    >>> mog(7, [3,2,2])
    0
    >>> mog(6, [1,4,1])
    1
    >>> mog(100, [100])
    99
    """
    printed = False
    previous_index = -1

    for i in range(0, day):
        ate_flag = False
        mog_maybe_index = get_max_index(num_cake)

        for n in mog_maybe_index:
            if n == previous_index:
                continue
            else:
                num_cake[n] = num_cake[n] - 1
                ate_flag = True
                previous_index = n
                break
        if ate_flag is False:
            try:
                mog_ext = get_second_max_index(num_cake)
                mogmog = mog_ext[0]
                if num_cake[mogmog] == 0:
                    printed = True
                    print(max(num_cake))

                    break
            except IndexError:
                print(max(num_cake))
                printed = True
                break
            num_cake[mogmog] = num_cake[mogmog] - 1
            previous_index = mogmog

    if printed is False:
        print(0)


if __name__ == "__main__":
    day, num_cake = read_input()
    mog(day, num_cake)

Submission status: Time Limit Exceeded

Solution code:
def read_input():
    l_1 = input()
    day = int(l_1.split(" ")[0])
 
    num_cake = [int(i) for i in input().split(" ")]
 
    return day, num_cake
 
def get_max_index(target_list):
    return [i for i, j in enumerate(target_list) if j == max(target_list)]
 
 
def get_second_max_index(target_list):
    return [i for i, j in enumerate(target_list) if j == list(sorted(set(target_list), reverse=True))[1]]
 
 
def mog(day, num_cake):
    """
 
    >>> mog(7, [3,2,2])
    0
    >>> mog(6, [1,4,1])
    1
    >>> mog(100, [100])
    99
    """
    printed = False
    previous_index = -1
 
    for i in range(0, day):
        # print("num_cake: ", num_cake)
        # print("previous_index: ",previous_index)
        ate_flag = False
        mog_maybe_index = get_max_index(num_cake)
        # print("mog_maybe_index: {0}".format(mog_maybe_index))
        for n in mog_maybe_index:
            if n == previous_index:
                continue
            else:
                num_cake[n] = num_cake[n] - 1
                ate_flag = True
                previous_index = n
                break
        if ate_flag is False:
            try:
                mog_ext = get_second_max_index(num_cake)
                # print("mog_ext", mog_ext)
                if num_cake[mog_ext[0]] == 0:
                    printed = True
                    print(max(num_cake))
                    break
            except IndexError:
                print(max(num_cake))
                printed = True
                break
            num_cake[mog_ext[0]] = num_cake[mog_ext[0]] - 1
            previous_index = mog_ext[0]
 
    if printed is False:
        print(0)

if __name__ == "__main__":
    #import doctest
    #doctest.testmod()
 
    day, num_cake = read_input()
    mog(day, num_cake)

Submission status: Time Limit Exceeded

Solution code:
def read_input():
    l_1 = input()
    day = int(l_1.split(" ")[0])
 
    num_cake = [int(i) for i in input().split(" ")]
 
    return day, num_cake
 
def get_max_index(target_list):
    return [i for i, j in enumerate(target_list) if j == max(target_list)]
 
 
def get_second_max_index(target_list):
    return [i for i, j in enumerate(target_list) if j == list(sorted(set(target_list), reverse=True))[1]]
 
 
def mog(day, num_cake):
    """
 
    >>> mog(7, [3,2,2])
    0
    >>> mog(6, [1,4,1])
    1
    >>> mog(100, [100])
    99
    """
    printed = False
    previous_index = -1
 
    for i in range(0, day):
        # print("num_cake: ", num_cake)
        # print("previous_index: ",previous_index)
        ate_flag = False
        mog_maybe_index = get_max_index(num_cake)
        # print("mog_maybe_index: {0}".format(mog_maybe_index))
        for n in mog_maybe_index:
            if n == previous_index:
                continue
            else:
                num_cake[n] = num_cake[n] - 1
                ate_flag = True
                previous_index = n
                break
        if ate_flag is False:
            try:
                mog_ext = get_second_max_index(num_cake)
                # print("mog_ext", mog_ext)
                if num_cake[mog_ext[0]] == 0:
                    printed = True
                    print(max(num_cake))
                    break
            except IndexError:
                print(max(num_cake))
                printed = True
                break
            num_cake[mog_ext[0]] = num_cake[mog_ext[0]] - 1
            previous_index = mog_ext[0]
 
    if printed is False:
        print(0)
 
 
 
if __name__ == "__main__":
    #import doctest
    #doctest.testmod()
 
    day, num_cake = read_input()
    mog(day, num_cake)

Submission status: Time Limit Exceeded

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

while len(a) > 1:
    a[-2] = abs(a[-1] - a[-2])
    while not a[-1]:
        a.pop()

if not a:
    print 0
else:
    print a[0] - 1

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
cakes = list(map(int, input().split()))
max_c = 0
sum_c = 0
for cake in cakes:
  max_c = max(max_c, cake)
  sum_c += cake
print(max(0, 2*max_c-sum_c-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
a=list(map(int,input().split()))
while len(a)>1:
  a.sort(reverse=True)
  a[0]-=a.pop()
print(max(0,a[0]-1))

Submission status: Accepted

Solution code:
import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()

k,t=lp()
a=lp()

x=max(a)

if k%2==0:
  if x<=(k//2):
    print(0)
  else:
    rest=k-x
    print(x-(rest+1))
    
else:
  if x<=(k//2)+1:
    print(0)
  else:
    rest=k-x
    print(x-(rest+1))

Submission status: Accepted

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

m = max(lis)
lis = sorted(lis)

if lis[-1:]:
    pass

if sum(lis[:-1]) >= m:
    print(0)
else:
    print(m-1-sum(lis[:-1]))

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


K,T = MI()
A = LI()
print(max(0,2*max(A)-K-1))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
A = sorted(map(int, input().split()))
if t == 1:
    print(k - 1)
else:
    dev = k - A[-1] + 1
    ans = max(0, (A[-1] // dev - 1) * dev + A[-1] % dev)
    print(ans)

Submission status: Accepted

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

m = max(al)
print(max(0, k-(k-m)*2-1))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K, T = mapint()
As = list(mapint())
maxi = max(As)
rest = K-maxi
if maxi<=rest+1:
    print(0)
else:
    maxi -= rest+1
    print(maxi)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    k, t = LI()
    a = LI()
    a.sort(reverse=True)

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


main()

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if K == T:
    print(0)
    exit()

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

b = a[0]
c = a[1]

for i in range(2, T):
    if b >= c:
        c += a[i]
    else:
        b += a[i]

print(max(abs(b - c) - 1, 0))

Submission status: Accepted

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

maxnum = max(A)
print(max(0, maxnum-1-(k-maxnum)))

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=[int(x) for x in input().split()]
a.sort()
now1=0
now2=0
al=sum(a)
ans=float('inf')
for i in range(t):
  now1+=a[i]
  now2=al-now1
  ans=min(ans,abs(now1-now2)-1)

if ans<=0:
  print(0)
else:
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
t, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if t%2==0:
    if t//2>=a[0]:
        ans = 0
    else:
        tmp = a[0] - (t//2)
        ans = 1 + 2*(tmp-1)
elif t%2!=0:
    if (t+1)//2>=a[0]:
        ans = 0
    else:
        tmp = a[0] - ((t+1)//2)
        ans = 2 * tmp

print(ans)

Submission status: Accepted

Solution code:
import heapq
from typing import List, Any, Tuple


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    K, T = read_ints()
    A = read_ints()
    cakes: List[List[int]] = [[-A[i], i] for i in range(T)]
    heapq.heapify(cakes)
    last_eaten = -1
    count = 0
    while cakes:
        frequent0 = heapq.heappop(cakes)
        if frequent0[1] == last_eaten:
            if cakes:
                frequent1 = heapq.heappop(cakes)
                last_eaten = frequent1[1]
                frequent1[0] += 1
                if frequent1[0] != 0:
                    heapq.heappush(cakes, frequent1)
            else:
                count += 1
                last_eaten = frequent0[1]
                frequent0[0] += 1
        else:
            frequent0[0] += 1
            last_eaten = frequent0[1]
        if frequent0[0] != 0:
            heapq.heappush(cakes, frequent0)
    return count


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

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

K, T = mi()
a = list(mi())

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()))
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()))
max_A = max(A)

if t == 1:
    print(k-1)
else:
    if max_A -1 > sum(A) - max_A:
        print((max_A -1) - sum(A) + max_A)
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

K,T=mint()
A=lint()
print(max(0,max(A)-(K-max(A))-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    K, T = MI()
    types = LI()

    types.sort(reverse=True)
    max_num = types[0]
    others_num = sum(types[1:])
    ans = max(max_num - 1 - others_num, 0)
    print(ans)


main()

Submission status: Accepted

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

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