Problem:


Score : 200 points

Problem Statement

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

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

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

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

Constraints

1 ≤ K ≤ 10000

1 ≤ T ≤ 100

1 ≤ a_i ≤ 100

a_1 + a_2 + ... + a_T = K

Input

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

K T
a_1 a_2 ... a_T

Output

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

Sample Input 1

7 3
3 2 2

Sample Output 1

0

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

Sample Input 2

6 3
1 4 1

Sample Output 2

1

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

Sample Input 3

100 1
100

Sample Output 3

99

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



Sample input:
7 3
3 2 2


Sample output:
0

Submission status: Accepted

Solution code:
# coding: utf-8
k, t = map(int,input().split())
A=list(map(int,input().split()))
m=max(A)
s=k-m
print(max(m-1-s, 0))

Submission status: Accepted

Solution code:
# coding: utf-8
import math
from collections import deque
import copy
import bisect
k, n = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
m=max(A)
s=k-m
print(max(m-1-s, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


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


def main():
    k, t = input_int_list()
    A = input_int_list()
    _max = max(A)
    ans = (_max - (k - _max)) - 1
    if ans < 0:
        ans = 0
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
def main():
    k,t=map(int,input().split())
    a=list(map(lambda x: (-int(x[1]), x[0]+1), enumerate(input().split())))
    heapq.heapify(a)
    p=None
    while len(a) > 0:
        n=heapq.heappop(a)
        if len(a) == 0:
            print(-n[0]-1)
            break
        if p == n[1] and len(a) > 0:
            n2 = n
            n = heapq.heappop(a)
            heapq.heappush(a, n2)
        if n[0] < -1:
            heapq.heappush(a, (n[0]+1, n[1]))
        p = n[1]
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

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

Submission status: Accepted

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

import heapq

k, t = list(map(int, input().split()))
cakes = list(map(lambda x: int(x)*-1, input().split()))
heapq.heapify(cakes)
ans = 0
top_change = True
for i in range(k):
    if top_change:
        first = heapq.heappop(cakes)
        first += 1
        if len(cakes) == 0:
            ans += first*-1
            break
        if first < cakes[0]:
            top_change = False
        else:
            top_change = True
        if first != 0:
            heapq.heappush(cakes, first)
    else:
        first = heapq.heappop(cakes)
        second = heapq.heappop(cakes)
        second += 1
        heapq.heappush(cakes, first)
        if second != 0:
            heapq.heappush(cakes, second)
        top_change = True

print(ans)

Submission status: Accepted

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

largest = max(a)
print(max(largest-(k-largest+1), 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W=list(map(int,input().split()))
l=list(map(int,input().split()))
l=[i*-1 for i in l]
import heapq
B=0
heapq.heapify(l)
for i in range(H):
   A=heapq.heappop(l)
   A+=1
   heapq.heappush(l,B)
   B=A
   l=[i for i in l if i!=0]
   if len(l)==0:
      print(H-1-i)
      exit()

Submission status: Accepted

Solution code:
import math
K,T=map(int,input().split())
A=list(map(int,input().split()))
if T==1:
    print(K-1)
else:
    half=math.ceil(K/2)
    ans=0
    for a in A:
        if a>half:
            ans+=(a-1-(K-a))
    print(ans)

Submission status: Accepted

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

b = 0
for i in a[::-1]:
    b = abs(b-i)
print(max(b-1, 0))

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    K, T = NMI()
    A = NLI()

    max_A = max(A)
    
    if T == 1:
        print(K-1)
    else:
        if max_A <= math.ceil(K/2):
            print(0)
        else:
            if K % 2 == 0:
                print(2*(max_A-math.ceil(K/2))-1)
            else:
                print(2*(max_A-math.ceil(K/2)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

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

m = max(nums)
rest = k - m
if m - rest - 1 > 0:
    print(m - rest - 1)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
a = list(map(int, input().split())) + [-N]
last = T
res = N
for t in range(N):
  x = T
  for i in range(T):
    if i == last: continue
    if a[x] <= a[i] and (a[i] > 0): x = i
  if x == T: x = last
  a[x] -= 1
  res -= x != last or (t == 0)
  last = x
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush


K, T, *A = map(int, open(0).read().split())
pq = [(-a, i) for i, a in enumerate(A)]
heapify(pq)

ans = 0
prev = -1
for _ in range(K):
    v, k = heappop(pq)
    if v == 0:
        heappush(pq, (v, k))
        ans += 1
    elif k != prev:
        prev = k
        heappush(pq, (v + 1, k))
    elif len(pq) > 1 and pq[0][0] < 0:
        v_nx, k_nx = heappop(pq)
        prev = k_nx
        heappush(pq, (v_nx + 1, k_nx))
        heappush(pq, (v, k))
    else:
        ans += 1
        heappush(pq, (v + 1, k))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
#mod = 10**9 + 7
#mod = 9982443453
mod = 998244353
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,t = readInts()
T = readInts()
ma = max(T)
rest = n - ma
print(max(0,ma - rest - 1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

prev = -1
ans = 0
for i in range(k):
    max_v = max(al)
    max_ind = al.index(max_v)
    max_v = 0
    max_i = -1
    for j, v in enumerate(al):
        if max_v < v and j != prev:
            max_v = v
            max_i = j
    if max_i != -1:
        al[max_i] -= 1
        prev = max_i
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

k,t = inm()
a = inl()
b = k-max(a)
print(max(0,k-1-2*b))

Submission status: Accepted

Solution code:

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

A = sorted(A, reverse=True)

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    K, T = map(int, readline().split())
    A = list(map(int, readline().split()))
    if sum(A)-max(A)+1 <max(A):
        print(max(A)*2-sum(A)-1)
    else:
        print(0)



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

ma = a[0]
ex = sum(a[1:])
diff =  ma - ex
if diff > 0:
    print(diff - 1)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
K, T = map(int, input().split())
a = tuple(map(int, input().split()))
cakes = []
heapq.heapify(cakes)
for i in range(T):
    heapq.heappush(cakes, [-1*a[i], i])
# print(cakes)
now = -1
ans = 0
for _ in range(K):
    cake_num, cake_idx = heapq.heappop(cakes)
    cake_num *= -1
    if cake_idx == now and len(cakes) > 1 and cakes[0][0] != 0:
        next_cake_num, next_cake_idx = heapq.heappop(cakes)
        next_cake_num *= -1
        next_cake_num -= 1
        heapq.heappush(cakes, [-1 * next_cake_num, next_cake_idx])
        now = next_cake_idx
    else:
        cake_num -= 1
        if now == cake_idx:
            ans += 1
        now = cake_idx
    heapq.heappush(cakes, [-1 * cake_num, cake_idx])
# print(cakes)
print(ans)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
a_m=0
sm =0
for i in range(1,t):
  if a[a_m] < a[i]:
    sm += a[a_m]
    a_m = i
  else:
    sm += a[i]

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

Submission status: Accepted

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

mt = max(t)

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

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:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal

INF = 1 << 50

def run():
    K, T, *A = map(int, read().split())
    max_a = max(A)
    print(max(max_a-1-K+max_a, 0))

if __name__ == "__main__":
    run()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    K, T = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    h = []
    for i in range(T):
        heapq.heappush(h, (-A[i], i))

    ans = 0
    p = -1

    while h:
        c = heapq.heappop(h)
        if p == c[1]:
            if h:
                c2 = heapq.heappop(h)
                heapq.heappush(h, c)
                x = c2[0]
                y = c2[1]
                p = y
                x += 1
                if x != 0:
                    heapq.heappush(h, (x, y))
            else:
                ans = c[0]
                break
        else:
            x = c[0]
            y = c[1]
            x += 1
            p = y
            if x != 0:
                heapq.heappush(h, (x, y))

    print(-ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
k, t, *a = map(int, open(0).read().split())
print(max(max(a)*2 - 1 - k, 0))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
k, t, *a = map(int, open(0).read().split())
a.sort()
c = [0]
for i in a:
    c.append(c[-1]+i)
print(min(abs(c[-1] - c[i]*2) - (c[-1]!= c[i]*2) for i in range(t+1)))

Submission status: Accepted

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

A.sort()
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()))

B=max(A)

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

if K%2:
    X=(K+1)//2
    if X>=B:
        print(0)
    else:
        C=B-X
        print(2*C)
else:
    Y=K//2
    if Y>=B:
        print(0)
    else:
        C=B-Y
        print(2*C-1)

Submission status: Accepted

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

B=max(A)

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

if K%2:
    X=(K+1)//2
    if X>=B:
        print(0)
    else:
        C=B-X
        print(2*C)
else:
    Y=K//2
    if Y>=B:
        print(0)
    else:
        C=B-Y
        print(2*C-1)

Submission status: Accepted

Solution code:
K,T=map(int,input().split())
*A,=map(int,input().split())
ans=0
H=0--K//2
for a in A:
    if a>H:
        ans+=2*a-K-1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[9]:


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


# In[10]:


if T == 1:
    ans = K-1
else:
    mylist = sorted(a)
    ans = max(mylist[-1]-sum(mylist[:-1])-1,0)
print(ans)

Submission status: Accepted

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

a.sort()

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

Submission status: Accepted

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

dp = [[False] * (k//2+1) for _ in range(t+1)]

dp[0][0] = True

for i in range(t):
    for j in range(k//2+1):
        if dp[i][j]:
            dp[i+1][j] = True
            if j + a[i] < k//2+1:
                dp[i+1][j + a[i]] = True

cnt = 0
for i,e in enumerate(dp[-1]):
    if e:
        cnt = i

ans = k - (2 * cnt + 1)

print(max(ans, 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()))

    prev_idx = -1
    ans = 0
    for _ in range(K):
        cur_idx = -1
        max_num = 0
        for i, a in enumerate(A):
            if i == prev_idx:
                continue
            if a > max_num:
                max_num = a
                cur_idx = i
        if max_num == 0:
            ans = A[prev_idx]
            break
        A[cur_idx] -= 1
        prev_idx = cur_idx

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

max_cake = max(a)

if max_cake >= K - max_cake:
    result = max_cake - (K - max_cake) - 1
else:
    result = 0

print(result)

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def solve():
    k, t= getList()
    nums = getList()
    mx = max(nums)
    if mx + mx - 1 <= k:
        print(0)
        return
    else:
        print(mx-1 - (k - mx))
        return
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = sorted(list(map(int, input().split())))
mx = l[-1]
s = sum(l[:-1])
print(max(0, mx-1-s))

Submission status: Accepted

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

Submission status: Accepted

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

x = max(a)
a.pop(a.index(max(a)))
y = sum(a)

if x > y:
  print(x-y-1)
else:
  print(0)

Submission status: Accepted

Solution code:
import sys
R1 = input().split()
R2 = input().split()
K = int(R1[0])
T = int(R1[1])
answer = int(0)
A = []
for i in range (0, T):
    A.append(int(R2[i]))
A.sort()
A.reverse()
if T == 1:
    print(A[0] - 1)
    sys.exit()
if T == 2:
    print(A[0] - A[1] - 1)
    sys.exit()
for i in range (0, K):
    C = A[0]
    if C - 1 > A[1]:
        if A[1] == 0:
            answer += 1
        if A[1] != 0:
            K -= 1
            D = int(A[1])
            A.remove(D)
            F = int(1)
            left = int(0)
            right = int(T - 2)
            while (left <= right):
                mid = int(left + (right - left) / 2)
                if A[mid] >= D - 1:
                    left = mid + 1
                    F = max(F, mid + 1)
                else:
                    right = mid - 1
            A.insert(F, D - 1)
        A[0] -= 1
    if C - 1 == A[1]:
        A[0] -= 1
    if C == A[1]:
        F = int(0)
        left = int(0)
        right = int(T - 1)
        while (left <= right):
            mid = int(left + (right - left) / 2)
            if A[mid] == C:
                left = mid + 1
                F = max(F, mid + 1)
            else:
                right = mid - 1
        A.insert(F, C - 1)
        A.remove(C)
print(answer)

Submission status: Accepted

Solution code:
def main():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    A.append(0)
    A.sort(reverse=True)
    ans =max(0, max(A) - sum(A[1:]) - 1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    k, t = map(int, readline().split())
    a = list(map(int, readline().split()))
    ans = 0
    prev = -1

    for _ in range(k):
        max_a = 0
        cur = -1
        for i in range(t):
            if i != prev:
                if a[i] > max_a:
                    max_a = a[i]
                    cur = i
        if cur != -1:
            a[cur] -= 1
            prev = cur

    print(sum(a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    K , T = [int(item) for item in input().split()]
    As = [int(item) for item in input().split()]
    As.sort(reverse=True)

    cnt = collections.Counter(As)
    interval_num = As[0]-1

    res = interval_num - sum(As[1:])

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
def main():
  k, t = map(int, input().split())
  a = list(map(int, input().split()))
  if t == 1:
    print(a[0]-1)
    sys.exit()
  a.sort(reverse = True)
  key = [0, 1]
  num = 0
  while True:
    k = num%2
    a[key[k]]-=1
    sub = 0
    if a[key[k]] == 0:
      key[k] = max(key) + 1
      if key[k] < t:
        if a[key[0]] >= a[key[1]]:k=0
        else:k = 1
        num = k-1
      else:
        sub = 1
        break
    num += 1
  print(sum(a)-sub)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = sorted(map(int, input().split()))
mv = a[-1]
nmv = sum(a[:-1])
# print(mv, nmv)
if nmv+1 <= mv:
    print(mv - nmv - 1)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(t-1):
    for j in range(i+1,t):
        if a[i] == 0:
            break
        x = min(a[i], a[j])
        a[i] -= x
        a[j] -= x
print(max(sum(a)-1, 0))

Submission status: Accepted

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

K,T = list(map(int,input().split()))
a = sorted(list(map(int,input().split())))
amax = a[-1]
asub = sum(a[0:-1])

print(max(0,amax-1-asub))

Submission status: Accepted

Solution code:
def main():
    import sys

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

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

    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

K, T = getNM()
A = getList()
A.sort(reverse = True)

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

Submission status: Accepted

Solution code:
K,T,*a = map(int, open(0).read().split())
a.sort()
print(max(0,a[-1]-sum(a[:T-1])-1))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    K, T = LI()
    a = LI()

    # aを2グループに分けて交互に食べれば良い
    # 最も差の少ない2グループの分け方を知りたい

    a.sort(reverse=True)
    a_cum = [0] * (T + 1)
    for i in range(T):
        a_cum[i+1] = a_cum[i] + a[i]

    ans = INF
    for i in a_cum:
        ans = min(max(abs(2 * i - K) - 1, 0), ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]  
    k, t = [int(x) for x in input().split()]  
    a = [int(x) for x in input().split()]  

    mx = max(a)
    el = k - mx
    print(max(0, mx - el - 1))
    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
a b a
d c d
a b a
"""

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
def main():
    k, t = map(int, input().split())
    A = list(map(lambda x: -int(x), input().split()))
    heapify(A)
    tmp = heappop(A)
    while A:
        now = heappop(A)
        if tmp != -1:
            heappush(A, tmp + 1)
        tmp = now
    print(-(tmp + 1))

if __name__ == '__main__':
    main()