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 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M = IL()
L = IL()
L.sort()

if L[-1] <= -(-N//2):
  print(0)
else:
  if N%2:
    print((L[-1]+(-N//2))*2)
  else:
    print((L[-1]+(-N//2))*2-1)

Submission status: Accepted

Solution code:
K,T = map(int, input().split())
a = list(map(int, input().split()))
lis = [0] * K
d = -1
T2 = T
for i in range(K):
    if T2 == 1:
        for j in range(T):
            if a[j] > 0:
                val = j
        lis[i] = val
    else:
        val = [0,0]
        for j in range(T):
            if j == d:
                continue
            if a[j] > val[0]:
                val = [a[j],j]
        a[val[1]] -= 1
        if a[val[1]] == 0:
            T2 -= 1

        lis[i] = val[1]
        d = val[1]

#print(lis)
ans = 0
for i in range(1,K):
    if lis[i] == lis[i-1]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

K, T = map(int, input().split())
A = list(map(lambda x, y: [int(x), y], sys.stdin.readline().rsplit(), range(T)))
A.sort(reverse=True)

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

res = 0
pre = -1
t = []
for k in range(K):
    if pre != A[0][1]:
        A[0][0] -= 1
        pre = A[0][1]
    elif pre == A[0][1] and A[1][0] > 0:
        A[1][0] -= 1
        pre = A[1][1]
    else:
        res += 1
    A.sort(reverse=True)

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

buf = []
heapq.heapify(buf)

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

for a in arr:
    heapq.heappush(buf,-a)

ans = 0

bef = None
while True:
    if not bef and len(buf) == 0:
        break
    if len(buf) == 0:
        ans += abs(bef)
        break
    else:
        top = heapq.heappop(buf)
        if bef:
            heapq.heappush(buf,bef)

        if top == -1:
            bef = None
        else:
            top += 1
            bef = top




    # print(buf,bef)


print(ans)

Submission status: Accepted

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

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

for i in range(k):#　i日目(i=0,1...k-1)
    [nex,ful] = sorted(a)[-2:]
    ful_index,nex_index = a.index(ful),a.index(nex)
    if nex == 0:
        ans = k-i-1
        break
    if last == ful_index:
        last = nex_index
        a[nex_index] -= 1
    else:
        last = ful_index
        a[ful_index] -= 1
        
print(ans)

Submission status: Accepted

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

maxi = max(a)
wa = sum(a)
print(max(0, maxi-1-(wa-maxi)))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a_list = list(map(int,input().split()))
a_max = a_list.pop(a_list.index(max(a_list)))

if t == 1:
  print(k-1)
  
else:
  if a_max - 1 >= sum(a_list):
    print(a_max - 1 - sum(a_list))
  else:
    print(0)

Submission status: Accepted

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

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

a = max(As)

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

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    k, t = map(int, input().split())
    A = list(map(int, input().split()))
    etc = sum(A) - max(A)
    res = max(0, max(A) - 1 - etc)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# Problem B - K個のケーキ

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

# initialization
a_nums = sorted(a_nums, reverse=True)
a_max = a_nums.pop(0)
a_sum = sum(a_nums)

# calc
check = a_max - a_sum - 1
if check>=0:
    print(check)
else:
    print(0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
a = A[0]
if a<=(K+1)//2:
    ans = 0
elif K%2==1:
    ans = (a-(K+1)//2)*2
else:
    ans = (a-(K+1)//2)*2-1
print(ans)

Submission status: Accepted

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

ans = A[0]-1
for a in A[1:]:
    ans -= a
    if ans < 0:
        ans = 0
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

Submission status: Accepted

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

Amax = max(A)
Asum = sum(A) - Amax

ans = max(0, Amax - Asum - 1)
print(ans)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
if t == 1:
    print(k-1)
    exit()

x = A[0]
s = sum(A)-A[0]
if s >= x:
    print(0)
else:
    ans = x-s-1
    print(max(ans, 0))

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

if len(l) == 0:
    print(l[0]-1)
    exit()

m = max(l)
s = sum(l)-m

if m-1 > s:
    print(m-s-1)
else:
    print(0)

Submission status: Accepted

Solution code:
'''
from math import gcd
from itertools import accumulate, combinations, permutations, product
from bisect import bisect, bisect_left
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop
from functools import reduce
from operator import add, mul, sub, truediv, floordiv, mod

from decimal import *
getcontext().prec = 500

import string
ascii = string.ascii_lowercase
'''
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    K, T = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort(reverse=1)
    cake = []
    x = []
    n = (K + 1) // 2
    for i in range(T):
        if A[i] > n:
            cake += [i] * n
            x += [i] * (A[i] - n)
        else:
            cake += [i] * A[i]
    cake += x
    turn = [0] * K
    j = 0
    for i in range(0, K, 2):
        turn[i] = cake[j]
        j += 1
    for i in range(1, K, 2):
        turn[i] = cake[j]
        j += 1
    ans = 0
    for i in range(1, K):
        ans += turn[i-1] == turn[i]
    print(ans)


main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
x=max(l)
if (n+1)//2+1>x:
  print(0)
else:
  print(x-1-(sum(l)-x))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    k, t = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()
    print(max(0, A[-1] - 1 - sum(A[:-1])))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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


def read():
    K, T = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return K, T, A


def solve(K, T, A):
    if T == 1:
        return K-1
    A.sort()
    return max(A[-1] - sum(A[:-1]) - 1, 0)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
K, T = map(int, sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort(reverse=True)
ans = A[0] - 1
for a in A[1:]:
    ans = max(0, ans - a)
print(ans)

Submission status: Accepted

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

A = sorted(A, reverse=True)
while len(A) > 1:
    A[0] -= 1
    A[-1] -=1
    if A[0] == 0:
        del A[0]
    if A[-1] == 0:
        del A[-1]

if A:
    print(A[0]-1)
else:
    print(0)

Submission status: Accepted

Solution code:
import heapq

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

hp = []
heapq.heapify(hp)
for i in input().split():
    heapq.heappush(hp, -int(i))

pre = -heapq.heappop(hp) - 1  
while hp:
    q = -heapq.heappop(hp)
    if pre > 0:
        heapq.heappush(hp, -pre)
    pre = q - 1
print(pre)

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 # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
k,t = readInts()
cake = readInts()
cake = sorted(cake)
if cake[-1] <= k/2:
    print(0)
else:
    print(k - (k- cake[-1]) * 2 - 1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    k, t = ns()
    a = na()
    a.sort()

    total = sum(a)-a[-1]

    ans = max(0, a[-1]-total-1)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i,an in enumerate(a):
    b.append([an,i])
ex = -1
ans = 0

if T == 1:
	print(K-1)
else:
  for i in range(K):
    list.sort(b, reverse=True)
    if ex == b[0][1] and b[1][0] != 0:
      b[1][0] -= 1
      ex = b[1][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
    else:
      b[0][0] -= 1
      if ex == b[0][1]:
        ans+=1
      ex = b[0][1]
      if b[0][1] == 0 and b[1][1] == 0:
        break
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Max = max(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
num_cakes, num_kinds = map(int,input().split())
kinds_ls = list(map(int, input().split()))
kinds_ls.sort()
max_value = kinds_ls[-1] - 1
else_sum = sum(kinds_ls[:num_kinds-1])

print(max(max_value-else_sum,0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,t,*a=map(int,open(0).read().split())
from math import *
print(max(0,(max(a)-ceil(n/2))*2-1))

Submission status: Accepted

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

maxi=max(a)
other = sum(a)-maxi
#print(maxi,other)

if maxi<=other:
    print(0)
else:
    print(maxi-other-1)

Submission status: Accepted

Solution code:
k,t=map(int,input().split())
a=list(map(int,input().split()))
sm=sum(a)
n=1
for i in a:
    if i>sm//2:
        n=i-(sm-i)
        break
print(n-1)

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
dat = list(map(int, input().split()))
dat.sort(reverse=True)
prev = -1
res = 0
eat = 0
if len(dat) == 1:
    print(dat[0] - 1)
else:
    dat.sort(reverse=True)
    while dat[1] != 0:
        x = dat[1]
        dat[0] -= x
        dat[1] = 0
        dat.sort(reverse=True)
    if dat[0] == 0:
        print(0)
    else:
        print(dat[0] - 1)

Submission status: Accepted

Solution code:
def m():
    K, T = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    a = A[0]
    b = sum(A[1:])
    if (a-b) <= 1:
        return 0
    else:
        return (a-b)-1


print(m())

Submission status: Accepted

Solution code:
import sys

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

if t == 1:
    print(sum(a) - 1)
    sys.exit()

max_a = max(a)

if (sum(a) + 1) // 2 >= max_a:
    print(0)
else:
    print(2 * max_a - sum(a) - 1)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq
k,t = map(int,input().split())
a = list(map(int,input().split()))
mx = max(a)
others = k - mx
if t == 1:
    print(k - 1)
    exit()

if others >= mx - 1:
    print(0)
else:
    print(mx - others - 1)

Submission status: Accepted

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

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

Submission status: Accepted

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

if t == 1:
    print(k-1)
else:
    a.sort(reverse=True)
    num = a[0] - 1
    cnt = 0
    for i in range(1, t):
        cnt += a[i]
    print(max(num-cnt, 0))

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    import heapq
    input = stdin.readline
    input()
    a = [-1 * int(i) for i in input().split()]
    heapq.heapify(a)
    while len(a) > 1:
        u = heapq.heappop(a)
        v = heapq.heappop(a)
        if u + 1 < 0:
            heapq.heappush(a, u + 1)
        if v + 1 < 0:
            heapq.heappush(a, v + 1)
    if len(a) == 0:
        print(0)
    else:
        print(abs(a[0] + 1))
main()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    input = stdin.readline
    k, _ = map(int, input().split())
    a = max(map(int, input().split()))
    print(max(0, 2 * a - k - 1))
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))

Submission status: Accepted

Solution code:
k, _, *a = map(int, open(0).read().split())
print(max(max(a)*2 - k - 1, 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,*a=map(int,open(0).read().split())
a.sort()
x=a[0]
ans=a[0]
for i in range(1,t):
  if x<a[i]:
    ans=+(a[i]-x)
  else:
    ans=0
  x+=a[i]
print(max(ans-1,0))

Submission status: Accepted

Solution code:
K, T = map(int, input().split())
A = list(map(int, input().split()))
ma = max(A)
if ma <= K//2:
    print(0)

else:
    print(ma - (K - ma + 1))

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
for i in range(t):
    a[i] = -a[i]
import heapq
heapq.heapify(a)
buf = heapq.heappop(a)+1
while len(a)>0:
    x = heapq.heappop(a)
    if buf!=0:
        heapq.heappush(a,buf)
    buf = x+1
print(-buf)

Submission status: Accepted

Solution code:
k,t = map(int,input().split())
A = list(map(int,input().split()))
M = max(A)
Os = sum(A)-M
if Os+1 >= M:
    print(0)
else:
    print(M-1-Os)

Submission status: Accepted

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    K, T = ZZ()
    A = ZZ()
    output = 0
    for a in A: output += max(0, a - (K - a + 2) + 1)
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
k, t = map(int, input().split())
a = list(map(int, input().split()))
a = [-i for i in a]
heapq.heapify(a)
while len(a) > 1:
    m = heapq.heappop(a)
    while m < 0 and len(a) > 0:
        n = heapq.heappop(a)
        if n <= m:
            heapq.heappush(a, n-m)
            m = 0
        else:
            m -= n
    if m < 0:
        heapq.heappush(a, m)
res = heapq.heappop(a)

print(max(-res-1, 0))

Submission status: Accepted

Solution code:
import sys

def main():
  n, t, *a = map(int, sys.stdin.read().split())
  a.sort()
  b = sum(a) - a[-1]
  a = a[-1]
  ans = max(0, a-(b+1))
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def min_day(A,K,T):
    if T == 1:
        return K-1
    else:
        A_max = max(A)
        if A_max <= K - A_max:
            return 0
        else:
            return K-2*(K-A_max)-1

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

    print(min_day(A,K,T))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if t == 1:
    print(k-1)
else:
    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()))

ans = 0
pre_index = 10**5
for i in range(k):
    max_value = 0
    max_index = 0
    for j in range(len(a)):
        if a[j] > max_value:
            max_value = a[j]
            max_index = j
    
    if pre_index != max_index:
        a[max_index] -= 1
        pre_index = max_index
    else:
        second_max_value = 0
        second_max_index = 0
        for j in range(len(a)):
            if j != max_index and a[j] > second_max_value:
                second_max_value = a[j]
                second_max_index = j
        if second_max_value == 0:
            a[max_index] -= 1
            pre_index = max_index
            ans += 1
        else:
            a[second_max_index] -= 1
            pre_index = second_max_index

print(ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    K, T = map(int, input().split())
    a = list(map(int, input().split()))
    if T == 1:
        print(K-1)
        return
    b = [-x for x in a]
    heapq.heapify(b)
    tmp = heapq.heappop(b)
    for i in range(K):
        tmp2 = heapq.heappop(b)
        if tmp2 == 0:
            break
        heapq.heappush(b, tmp+1)
        tmp = tmp2
    print(K-1-i)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
k,t = map(int,input().split())
a = list(map(int,input().split()))
pre = a.index(max(a))
res = 0
while k>0:
    a[pre] -=1
    k -=1
    if k==0:
        break
    else:
        Conf=[]
        Conf = a[:]
        if t>1:
            Conf[pre] = -1
            preV = max(Conf)
            prei = a.index(preV)
            if preV==0:
                res+=1
            else:
                pre = prei
        else:
            res+=1
print(res)

Submission status: Accepted

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

K, T = list(map(int, input().split()))
a_list = list(map(int, input().split()))
a_list = sorted(a_list)
k = K

if T == 1:
    count = K - 1
elif T == 2:
    diff = a_list[-1] - a_list[-2]
    if diff <= 1:
        count = 0
    else:
        count = diff - 1
else:
    # 一番多いケーキと2番目に多いケーキの個数の差
    diff = a_list[-1] - a_list[-2]
    if diff <= 1:
        count = 0
    else:
        x = sum(a_list[:-2])
        if (a_list[-1] - 1) <= (a_list[-2] + x):
            count = 0
        else:
            count = a_list[-1] - (a_list[-2] + x) - 1
ans = count
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    mv=max(A)
    mi=A.index(mv)

    rem=sum(A)-mv
    print(max(0,mv-1-rem))
    

    

    
resolve()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
k, t = map(int, input().split())
a = list(map(int, input().split()))

que = []
heapify(que)

for i in range(t):
    heappush(que, (-a[i], i))

s = [-1]
while len(que) > 0:
    if len(que) == 1:
        a_i, idx = heappop(que)
        for _ in range(-a_i):
            s.append(idx)
        break
    else:
        a_i, idx_i = heappop(que)
        if s[-1] == idx_i:
            a_j, idx_j = heappop(que)
            s.append(idx_j)
            heappush(que, (a_i, idx_i))
            a_j += 1
            if a_j < 0:
                heappush(que, (a_j, idx_j))
        else:
            s.append(idx_i)
            a_i += 1
            if a_i < 0:
                heappush(que, (a_i, idx_i))

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

Submission status: Accepted

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

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:
import sys

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

if len(A) == 1:
    print(A[0] - 1)
else:    
    A.sort(reverse=True)
    other_sum = sum(A[1:])
    print(max(0, A[0] - other_sum - 1))

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:
K,T = map(int,input().split())
a = list(map(int,input().split()))
m = max(a)
print(max(0,m-1-(K-m)))

Submission status: Accepted

Solution code:
from collections import deque
k,t = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
a = deque(a)
length = len(a)
if length ==1:
    print(sum(a)-1)
    exit()
while length > 1:
    mx = a.pop()
    mn = a.popleft()
    mx -= 1
    mn -= 1
    if mx != 0:
        a.append(mx)
    else:
        length -=1
    if mn != 0:
        a.appendleft(mn)
    else:
        length-=1    
print(max(sum(a)-1,0))

Submission status: Accepted

Solution code:
k, t = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
double_cnt = 0
total = 0
for i in range(t):
  b = a[i] - double_cnt
  c = total - (double_cnt + 1) + 2
  double_cnt = max(0, b-c)
  total += a[i]
print(double_cnt)

Submission status: Accepted

Solution code:
def main():
    K, T = map( int, input().split())
    A = list( map( int, input().split()))
    A.sort(reverse=True)
    if A[0] <= (K+1)//2:
        print(0)
    else:
        print((A[0] - (K+1)//2)*2 - (K+1)%2)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K,T = map(int,input().split())
from heapq import heapify, heappop, heappush
A = list(map(int,input().split()))
for i in range(T):
    A[i] = (-A[i],i)
A.append((0,999))
A.sort()
heapify(A)
ans = 0
pre = -1

for i in range(K):
    a,i = heappop(A)
    if pre != i:
        heappush(A,(a+1,i))
        pre = i
    else:
        a2,i2 = heappop(A)
        if a2 < 0:
            pre = i2
            heappush(A,(a2+1,i2))
            heappush(A,(a,i))
        else:
            ans += 1
            heappush(A,(a+1,i))
            heappush(A,(a2,i2))
print(ans)

Submission status: Accepted

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

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

a_l = []
for i, a in enumerate(a_l_init):
    a_l.append([a,i])
a_l.sort(reverse=True)

flag = 0
yesterday = -1
for _ in range(k):
    for j in range(t):
        if a_l[j][1] != yesterday:
            a_l[j][0] -= 1
            yesterday = a_l[j][1]
            a_l.sort(reverse=True)
            break
        elif a_l[j+1][0] != 0:
            continue
        else:
            flag = 1
            break
    if flag == 1:
        break

if flag == 0:
    print(0)
else:
    print(a_l[0][0])