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
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    k, t = MII()
    aa = MII()
    aa.sort(reverse=True)
    ans = max(aa[0]-1-(k-aa[0]), 0)
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

# スペース
space = A[0] - 1
for x in A[1:]:
    space -= x

print(max(0, space))

Submission status: Accepted

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

if suma - maxa >= maxa - 1:
    print(0)
else:
    print(maxa - 1 - (suma-maxa))

Submission status: Accepted

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

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

A = list(reversed(sorted(A)))

left_sum = 0
right_sum = 0
for i in A:
    if left_sum < right_sum :
        left_sum += i
    else:
        right_sum += i

if abs(left_sum - right_sum) in [0, 1]:
    print(0)
else:
    a = abs(left_sum - right_sum) - 1
    print(a)

Submission status: Accepted

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

table = [False] * (K + 1)

table[0] = True

for n in numbers:
  for i in range(K, 0, -1):
    if i - n >= 0:
      table[i] = table[i] or table[i - n]
    
m = 0

for i, t in enumerate(table):
  if not t:
    continue
  m = i if abs(i - K / 2) < abs(m - K / 2) else m

if abs(2 * m - K) <= 1:
  print(0)
else:
  print(abs(2 * m - K) - 1)

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_input = list(map(int,input().split()))

#最も多いケーキをAtとする,a=4,b=1,c=1の場合を考えると
#a,b,a,c,a,aのようになる。よってa-(b+c)-1
max_a = max(a_input)
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()))
ma = max(a)
s = sum(a) - ma
print(max(0, ma - s - 1))

Submission status: Accepted

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

b=a[0]
c=a[1]
for i in range(2,T):
    if b>c:
        c+=a[i]
    else:
        b+=a[i]
if b==c:
    print(0)
    exit()
print(abs(b-c)-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def codefes16q_b():
    _, _ = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    x = 2 * A[-1] - sum(A)
    ans = max(x-1, 0)
    print(ans)

codefes16q_b()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
k,t=mii()
arr=sorted(limii(),reverse=True)

if t==1:
    print(k-1)
    exit()
if arr[0]-1 <=sum(arr[1:]):
    print(0)
else:
    print(arr[0]-sum(arr[1:])-1)

Submission status: Accepted

Solution code:
def get_max(aa):
    mi = None
    for i,v in aa.items():
        if mi is None or v > mv:
            mi = i
            mv = v
    return mi

def main():
    k,t=map(int,input().split())
    aa={i:v for i,v in enumerate(map(int,input().split()),1)}
    mi = None
    while len(aa) > 1:
        mi = get_max({i:v for i,v in aa.items() if i != mi})
        if aa[mi] > 1:
            aa[mi]-=1
        else:
            del aa[mi]
    print(list(aa.values())[0]-1)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import functools
import math
import scipy
import fractions
import itertools
 
def solve():
    k, t = map(int, input().split())
    a = list(map(int, input().split()))
    print(max(0, max(a)-(sum(a)-max(a))-1))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    K, T = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    print(max(0, max(A)-(sum(A)-max(A))-1))

if __name__ == '__main__':
     main()

Submission status: Accepted

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

Submission status: Accepted

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

ans = max(0,max(A)-1-(sum(A)-max(A)))

print(ans)

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = list(map(int,input().split()))
minA = min(A)
maxA = max(A)
sumA = sum(A)

if len(A) == 1:
  ans = A[0]-1
else:
  ans = max(0,maxA-1-(sumA-maxA))

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

k, t = na()
a = na()

s = sum(a)
a.sort()
s -= a[-1]
if a[-1] - s <= 0:
    print(0)
else:
    print(a[-1] - s - 1)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


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

    ans = 0
    prev_j = -1
    for i in range(K):
        j_max = 0
        n_max = 0
        for j in range(T):
            if j == prev_j:
                continue
            if a[j] > n_max:
                n_max = a[j]
                j_max = j
        if n_max == 0:
            ans += 1
        else:
            prev_j = j_max
            a[j_max] -= 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    K,T=pin()
    A=tupin()
    B=[[A[i],i] for i in range(T)]
    #print(B)
    prev=None
    for k in range(K):
        B.sort(key=lambda x:x[0])
    #    print(B,"#")
        for i in reversed(range(T)):
            if B[i][0]>0 and B[i][1]!=prev:
                B[i][0]-=1
                
                prev=B[i][1]
                break
    print(sum([B[k][0] for k in range(T)]))
#%%submit!
resolve()

Submission status: Accepted

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

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

maxt = max(t)

print(max(0, maxt-1-(k-maxt)))

Submission status: Accepted

Solution code:

K,T = map(int,input().split())
a = list(map(int,input().split()))
x = max(a)

print(max(x-1-(K-x),0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

goods = K - max(As)
ans = K - goods * 2

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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


most = max(a)
hasami = k-most

print(max(0,most-hasami-1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    _, _ = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    max_a = max(a)
    d = sum(a) - max_a
    d = max_a - d
    print(max(0, d - 1))


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

x = max(a)
y = (k - x)

r = x - y - 1
print(max(0, r))

Submission status: Accepted

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

k, t = map(int, input().split())
nums = [int(i) for i in input().split()]
MAX = max(nums)

ans = max(MAX - 1 - (k - MAX), 0)
print(ans)

Submission status: Accepted

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

if len(a)>1:
    x=a[0]-sum(a[1:])
    if x>0:
        print(x-1)
    else:
        print(0)
else:
    print(a[0]-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10 **9 + 7
INF = 10 ** 10
from heapq import heapify,heappop,heappush

def main():
    k,t = map(int,input().split())
    A = list(map(int,input().split()))
    if t == 1:
        print(k - 1)
        return
    A = [(-A[i],i) for i in range(t)]
    heapify(A)
    
    before = -1
    ans = 0
    for _ in range(k):
        p,i = heappop(A)
        if i != before:
            p += 1
            before = i
            heappush(A,(p,i))
        else:
            q,j = heappop(A)
            if q < 0:
                q += 1
                before = j
                heappush(A,(q,j))
                heappush(A,(p,i))
            else:
                p += 1
                ans += 1
                heappush(A,(p,i))
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
k,t=map(int,input().split())
a=list(map(lambda x:-int(x),input().split()))
a.sort()
import heapq
heapq.heapify(a)
b=heapq.heappop(a)
b+=1
while len(a)>0:
    c=heapq.heappop(a)
    if b<0:
        heapq.heappush(a,b)
    b=c+1
print(-b)

Submission status: Accepted

Solution code:
# CODE FESTIVAL 2016 予選 C: B – K個のケーキ / K Cakes
K, T = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]

max_index = a.index(max(a))

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

Submission status: Accepted

Solution code:
import heapq

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

heapq.heapify(a)
cake_yesterday = -1
ans = 0

for i in range(K):
    cake1 = heapq.heappop(a)
    if cake1[1] != cake_yesterday:
        cake_yesterday = cake1[1]
        if cake1[0]+1 <= -1:
            heapq.heappush(a, (cake1[0]+1, cake1[1]))
    elif a:
        cake2 = heapq.heappop(a)
        cake_yesterday = cake2[1]
        heapq.heappush(a, (cake1[0], cake1[1]))
        if cake2[0]+1 <= -1:
            heapq.heappush(a, (cake2[0]+1, cake2[1]))
    else:
        if cake_yesterday == cake1[1]:
            ans += 1
        ans += -cake1[0] - 1
        break

print(ans)

Submission status: Accepted

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

    a.sort(reverse=True)
    greatest = a[0]
    others = sum(a[1:])

    if greatest - others <= 1:
        print(0)
        return
    else:
        print(greatest-others-1)
        return

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def log(*args):
    print(*args, file=sys.stderr)


K, T = map(int, input().split())
counts = map(int, input().split())
counts = sorted(counts, reverse=True)
print(max(0, counts[0] - (sum(counts) - counts[0]) - 1))

Submission status: Accepted

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

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

from collections import deque
B = deque(C)
L = [-1]*k
for i in range(k):
    if i%2 == 0:
        L[i] = B.popleft()
    else:
        L[i] = B.pop()

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

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

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

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
#3問目 CODE FESTIVAL 2016 qual C B問題 -K個のケーキ
KT = map(int, input().split())
A = [int(s) for s in input().split()]
Max_i = 0
Max = 0
withoutMaxSum = 0
#二回連続で食べる可能性のあるケーキは一番個数の多いケーキのみ
#一番個数の多いケーキの個数 - その他のケーキの個数の総和 - 1が前日と同じケーキを食べる日数
#0以下になったら確実に被らずに食べられる
#1以上になったら確実に被る -> max(0, Max - withoutMaxSum)
for i in range(len(A)):
    if(Max < A[i]):
        Max = A[i]
        Max_i = i
for i in range(len(A)):
    if(i != Max_i):
        withoutMaxSum += A[i]
print(max(0, Max-withoutMaxSum-1))

Submission status: Accepted

Solution code:
#3問目
KT = input().split()
K,T = int(KT[0]), int(KT[1])
A = input().split()
intA = [int(s) for s in A]
saidai_i = 0
saidai = 0
withoutSaidaiSum = 0
for i in range(len(intA)):
    if(saidai < intA[i]):
        saidai = intA[i]
        saidai_i = i
for i in range(len(intA)):
    if(i != saidai_i):
        withoutSaidaiSum += intA[i]
print(max(0, saidai-withoutSaidaiSum-1))

Submission status: Accepted

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

maxA = max(a)
# print(a)
t = a.index(maxA)
# 最大を置いて，間に挟んでいく
# 間に挟める個数はk - a[t]個ある
# a[t] - 1個はdefault
ans = max(a[t] - 1 - (k - a[t]), 0)
print(ans)

Submission status: Accepted

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

k, t, *a = map(int, read().split())
print(max(0, 2 * max(a) - k - 1))

Submission status: Accepted

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

K, T = MAP()
a = LIST()
ma = max(a)
left = sum(a)-ma
print(max(0, ma-left-1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k, t = map(int, input().split())
    A = list(map(int, input().split()))
    B = []
    for i in range(t):
        B.append([i + 1, A[i]])
    B = sorted(B, key=lambda x: x[1])

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

    res = 0
    pre = 0
    for i in range(k):
        if pre != B[-1][0]:
            pre = B[-1][0]
            B[-1][1] -= 1
            B = sorted(B, key=lambda x: x[1])
        else:
            if B[-2][1] != 0:
                pre = B[-2][0]
                B[-2][1] -= 1
                B = sorted(B, key=lambda x: x[1])
            else:
                B[-1][1] -= 1
                res += 1

    print(res)


if __name__ == '__main__':
    resolve()

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

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


if __name__ == '__main__':
    K, T = map(int, input().split())
    A = list(map(int, input().split()))

    que = queue.PriorityQueue()
    for a in A:
        que.put(-a)

    que2 = queue.Queue()

    ans = 0
    while not que.empty():
        n = -que.get()
        if not que2.empty():
            que.put(que2.get())
        if que.empty():
            ans += 1
            if n - 1 > 0:
                n -= 1
                que.put(-n)
                continue
            else:
                break
        if n - 1 > 0:
            n -= 1
            que2.put(-n)

    print(ans - 1)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

M = max(a)
ans = max(M - 1 - (K - M), 0)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

print(max(0,y-x-1))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
aaa = list(map(int, input().split()))
m = max(aaa)
if m <= (k + 1) // 2:
    print(0)
    exit()

others = k - m
print(k - (others * 2 + 1))

Submission status: Accepted

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

if t == 1:
  ans = k-1
else:
  key = max(a)
  if key <= (k+1)//2:
    ans = 0
  else:
    ans = 2*key-k-1

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    k,t = LI()
    a = LI()
    q = []
    for i in a:
        heappush(q,-i)
    while len(q) > 1:
        x = heappop(q)
        y = heappop(q)
        x += 1
        y += 1
        if x:
            heappush(q,x)
        if y:
            heappush(q,y)
    if not q:
        print(0)
    else:
        print(-q[0]-1)
    return

#Solve
if __name__ == "__main__":
    solve()

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:
import heapq
K,T=map(int,input().split(' '))
A=[[-i,n] for n,i in enumerate(list(map(int,input().split(' '))))]
heapq.heapify(A)
A_max = heapq.heappop(A)
today = A_max[1]
if A_max[0]<-1:
    heapq.heappush(A,[A_max[0]+1,today])
while len(A)>1:
    a=heapq.heappop(A)
    b=heapq.heappop(A)
    if today!=a[1]:
        today = a[1]
        a[0] += 1
    else:
        today = b[1]
        b[0] += 1
    if a[0]<0:
        heapq.heappush(A,a)
    if b[0]<0:
        heapq.heappush(A,b)
if today != A[0][1]:
    print(-A[0][0]-1)
else:
    print(-A[0][0])

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline

K, T = map(int, readline().split())
A = sorted(list(map(int, readline().split())))[::-1]

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

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

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

print(cnt)

Submission status: Accepted

Solution code:
K,T = list(map(int,input().split(" ")))
nums = list(map(int,input().split(" ")))
ma = max(nums)
s  = sum(nums) - ma
ans = ma  - 1
ans = max(0,ans -s )
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
ma=a[0]
su=sum(a)
res=su-ma
if T==1:
    print(su-1)
else:
    print(max(ma-res-1,0))

Submission status: Accepted

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

Submission status: Accepted

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

if T == 1:
    print(K - 1)
else:
    M = max(a)
    rest = sum(a) - M

    if rest >= M - 1:
        print(0)
    else:
        print(M - rest - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, 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())
a = sorted(list(map(int, input().split())))[::-1]
ans = a[0]-1

for i in range(1, T):
    ans -= a[i]
    if ans < 0:
        print(0)
        exit()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush,heapify,heappop
k,t=map(int,input().split())
a=list(map(int,input().split()))
b=[]
heapify(b)
ans=[-1]*k
for i in range(t):
    heappush(b,[-a[i],i])
x=heappop(b)
ans[0]=x[1]
x[0]+=1
if x[0]<0:
    heappush(b,x)
for i in range(1,k):
    x=heappop(b)
    if ans[i-1]==x[1] and b:
        y=heappop(b)
        ans[i]=y[1]
        y[0]+=1
        if y[0]<0:
            heappush(b,y)
        heappush(b,x)
    else:
        ans[i]=x[1]
        x[0]+=1
        if x[0]<0:
            heappush(b,x)
cnt=0
for i in range(1,k):
    if ans[i]==ans[i-1]:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def main():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    max_a = max(A)
    limit = (K + 1)//2
    if max_a <= limit:
        print(0)
    else:
        remain = K - max_a
        print(max_a - remain - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

al.sort(reverse=True)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True) #大きい順
ans=A[0]-1 #被る日
for i in range(1,T): 
    ans-=A[i]
    if ans<0:
        ans=0
        break
print(ans)

Submission status: Accepted

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

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

cnt = 0
for i in range(len(A)):
    if A[i] >= 1:
        cnt += 1
print(max(A) - cnt)

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()))
M=max(a)
sm=sum(a)
if (2*M)<=sm:
    print(0)
else:
    ans=2*M-sm
    print(ans-1)

Submission status: Accepted

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

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

Submission status: Accepted

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

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


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


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

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

Submission status: Accepted

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

Submission status: Accepted

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

ai.sort(reverse=True)

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    K, T = MI()
    a = LI()
    q = deque()

    for i in range(K):
        mx = 0
        mx_i = -1
        for j in range(T):
            if a[j] > mx and ((len(q) > 0 and q[-1] != j) or len(q) == 0):
                mx = a[j]
                mx_i = j

        if mx_i != -1:
            a[mx_i] -= 1
            q.append(mx_i)

    print(sum(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ma = max(a)
sa = sum(a)
d = sa - ma

print(max(ma-(d+1),0))