Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys

N_MAX = 100010

sys.setrecursionlimit(100000)

dp = [-1]*N_MAX
vec = [0]*N_MAX

def frog(n):
  if dp[n] != -1:
    return dp[n]
  else:
    dp[n] = min(frog(n-1) + abs(vec[n] - vec[n-1]) , frog(n-2) + abs(vec[n] - vec[n-2]))
    return dp[n]
  
N = int(input())
ln = list(map(int, input().split()))

for i in range(N):
  vec[i] = ln[i]

dp[0] = 0
dp[1] = abs(vec[0] - vec[1])

print(frog(N-1))


  

Fixed submission:
import sys

N_MAX = 100010

sys.setrecursionlimit(500000)

dp = [-1]*N_MAX
vec = [0]*N_MAX

def frog(n):
  if dp[n] != -1:
    return dp[n]
  else:
    dp[n] = min(frog(n-1) + abs(vec[n] - vec[n-1]) , frog(n-2) + abs(vec[n] - vec[n-2]))
    return dp[n]
  
N = int(input())
ln = list(map(int, input().split()))

for i in range(N):
  vec[i] = ln[i]

dp[0] = 0
dp[1] = abs(vec[0] - vec[1])

print(frog(N-1))

Buggy python submission (verdict: Runtime Error):
import sys

N_MAX = 100010

dp = [-1]*N_MAX
vec = [0]*N_MAX

def frog(n):
  if dp[n] != -1:
    return dp[n]
  else:
    dp[n] = min(frog(n-1) + abs(vec[n] - vec[n-1]) , frog(n-2) + abs(vec[n] - vec[n-2]))
    return dp[n]
  
N = int(input())
ln = list(map(int, input().split()))

for i in range(N):
  vec[i] = ln[i]

dp[0] = 0
dp[1] = abs(vec[0] - vec[1])

print(frog(N-1))

  

Fixed submission:
import sys

N_MAX = 100010

sys.setrecursionlimit(500000)

dp = [-1]*N_MAX
vec = [0]*N_MAX

def frog(n):
  if dp[n] != -1:
    return dp[n]
  else:
    dp[n] = min(frog(n-1) + abs(vec[n] - vec[n-1]) , frog(n-2) + abs(vec[n] - vec[n-2]))
    return dp[n]
  
N = int(input())
ln = list(map(int, input().split()))

for i in range(N):
  vec[i] = ln[i]

dp[0] = 0
dp[1] = abs(vec[0] - vec[1])

print(frog(N-1))
Buggy python submission (verdict: Runtime Error):
S = input()
c = 0
ans = 0
for i in range(3):
  if S[i] == 'R':
    c++
  else:
    ans = max(c,ans)
print(ans)

Fixed submission:
S = input()
c = 0
ans = 0
for i in range(3):
  if S[i] == 'R':
    c+=1
  else:
    ans = max(c,ans)
    c = 0
ans = max(c,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
print((1000-(int(input)%1000))%1000)

Fixed submission:
print((1000-(int(input())%1000))%1000)

Buggy python submission (verdict: Runtime Error):
print((1000-int(input)%1000)%1000)

Fixed submission:
print((1000-(int(input())%1000))%1000)
Buggy python submission (verdict: Runtime Error):
a = [input() for _ in range(int(input()))]
print("AC x {0}".format(a.count("AC"))
print("WA x {0}".format(a.count("WA"))
print("TLE x {0}".format(a.count("TLE"))      
print("RE x {0}".format(a.count("RE"))

Fixed submission:
a = [input() for _ in range(int(input()))]
print("AC x {}".format(a.count("AC")))
print("WA x {}".format(a.count("WA")))
print("TLE x {}".format(a.count("TLE")))
print("RE x {}".format(a.count("RE")))

Buggy python submission (verdict: Runtime Error):
a = [input() for _ in range(int(input())]
print("AC x {0}".format(a.count("AC"))
print("WA x {0}".format(a.count("WA"))
print("TLE x {0}".format(a.count("TLE"))      
print("RE x {0}".format(a.count("RE"))

Fixed submission:
a = [input() for _ in range(int(input()))]
print("AC x {}".format(a.count("AC")))
print("WA x {}".format(a.count("WA")))
print("TLE x {}".format(a.count("TLE")))
print("RE x {}".format(a.count("RE")))
Buggy python submission (verdict: Runtime Error):
s = input()
ans = ""
for c in s:
  if c == '?':
    ans.append('d')
  else:
    ans.append(c)
print(ans)

Fixed submission:
s = input().replace("?", "D")
print(s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    k=i+1
    B = A[:]
    B.pop(i)
    C = [0]*(N+1)
    for l in range(N-1):
        C[B[l]] += 1
    temp = 0
    for m in range(N-1):
        temp += int(C[m]*(C[m]-1)/2)
    print(temp)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

B = [0]*(N+1)
for l in range(N):
    B[A[l]] += 1
ans = 0
for i in range(N+1):
    ans += int(B[i] * (B[i]-1) / 2)
for k in range(N):
        print(ans - B[A[k]] + 1)

Buggy python submission (verdict: Runtime Error):
import copy

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

for i in range(N):
    k=i+1
    B = copy.copy(A)
    B.pop(i)
    C = [0]*(N-1)
    for l in range(N-1):
        C[B[l]] += 1
    temp = 0
    for m in range(N-1):
        temp += int(C[m]*(C[m]-1)/2)
    print(temp)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

B = [0]*(N+1)
for l in range(N):
    B[A[l]] += 1
ans = 0
for i in range(N+1):
    ans += int(B[i] * (B[i]-1) / 2)
for k in range(N):
        print(ans - B[A[k]] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N, K, Q = list(map(int, input().split()))
A = [int(input()) for i in range(Q)]
P = [K for i in range(N)]
for i in range(Q):
        for j in range(N):
                if j==A[i]-1:
                        continue
                else:
                        P[j] -= 1
for i in range(N):
        if P[i] <= 0:
                print("No")
        else:
                print("Yes")

Fixed submission:
N, K, Q = list(map(int, input().split()))
A = [int(input()) for i in range(Q)]
num = [0 for i in range(N)]
for i in range(Q):
        num[A[i]-1] += 1
for i in range(N):
        if Q-K < num[i]:
                print("Yes")
        else:
                print("No")
Buggy python submission (verdict: Runtime Error):
import itertools
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in itertools.combinations(arr, 3):
  if i[0]+i[1] > i[3] and i[0]+i[3] > i[1] and i[3]+i[1] > i[0]:
    count += 1
print(count)
    
  


Fixed submission:
import itertools

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in itertools.combinations(arr, 3):
    if i[0] + i[1] > i[2] and i[0] + i[2] > i[1] and i[2] + i[1] > i[0] and i[0] != i[1] != i[2]:
        count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
import math
n, d = list(map(int, input().split()))
count = 0
for _ in range(n):
  x, y = list(map(int, input().split()))
  if math.sqrt(x**2 + y**2) >= d
  count += 1
print(count)

Fixed submission:
import math
n, d = list(map(int, input().split()))
count = 0
for _ in range(n):
  x, y = list(map(int, input().split()))
  if math.sqrt(x**2 + y**2) <= d:
    count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
arr = []
for _ in range(int(input())):
  arr.append(int(input()))
arr2 = arr.copy()
for k in range(len(arr)):
  arr.pop(k)
  print(max(arr))
  arr = arr2.copy()

Fixed submission:
arr = []
for _ in range(int(input())):
  arr.append(int(input()))
arr2 = arr.copy()
arr2.sort()
z = arr2[-1]
zz = arr2[-2]
for k in arr:
  if k != z:
    print(z)
  else:
    print(zz)
Buggy python submission (verdict: Runtime Error):
arr = list(map(int, input().split()))
for k in range(len(arr)):
  if arr[k] == arr[k+1]:
    print("Bad")
    exit()
print("Good")

Fixed submission:
arr = list(input())
for k in range(len(arr) - 1):
  if arr[k] == arr[k+1]:
    print("Bad")
    exit()
print("Good")
Buggy python submission (verdict: Runtime Error):
s = list(input())
z = s.copy()
arr = []
result = []
req = list("AKIHABARA")
if s == []:
    print("NO")
    exit()
while s.count("A") >= 1:
    result.append(s.index("A"))
    s.remove("A")
m = "".join(z)
k = z.index("K")
for d in range(len(result)-1):
    if result[d] - result[d+1] == 0:
        print("NO")
        exit()
    else:
        arr.append("T")
if s == ['K', 'I', 'H', 'B', 'R'] and s.count("A") <= 4 and "KIH" in m:
    if "T" in arr or arr == [] or len(result) == 1:
        print("YES")
else:
    print("NO")

Fixed submission:
import re
print("YES" if re.match(r"^A?KIHA?BA?RA?$", input()) else "NO")

Buggy python submission (verdict: Runtime Error):
s = list(input())
z = s.copy()
arr = []
result = []
req = list("AKIHABARA")
while s.count("A") >= 1:
    result.append(s.index("A"))
    s.remove("A")
m = "".join(z)
k = z.index("K")
for d in range(len(result)-1):
    if result[d] - result[d+1] == 0:
        print("NO")
        exit()
    else:
        arr.append("T")
if s == ['K', 'I', 'H', 'B', 'R'] and s.count("A") <= 4 and "KIH" in m:
    if "T" in arr or arr == [] or len(result) == 1:
        print("YES")
else:
    print("NO")

Fixed submission:
import re
print("YES" if re.match(r"^A?KIHA?BA?RA?$", input()) else "NO")
Buggy python submission (verdict: Runtime Error):
N = int(input())
l = []
for _ in range(N):
    l.append(input())

from collections import Counter

co = Counter(l).most_common()
l = [co[0][0]]

for n in range(N):
    if co[n+1][1] == co[n][1]:
        l.append(co[n+1][0])
    else:
        break
l.sort()

for n in range(len(l)):
    print(l[n])

Fixed submission:
N = int(input())
l = []
for _ in range(N):
    l.append(input())

from collections import Counter

co = Counter(l).most_common()
l = [co[0][0]]

for n in range(len(co)-1):
    if co[n+1][1] == co[n][1]:
        l.append(co[n+1][0])
    else:
        break
l.sort()

for n in range(len(l)):
    print(l[n])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
List = list(map(int, input().split()))

count = 'YES'
for i in range(max(List)):
    List = list(map(lambda x:x-1, List))
    if List.count(0) == 2:
        count = 'NO'

print(count)

Fixed submission:
N = int(input())
List = list(map(int, input().split()))

List.sort()
count = 'YES'
for i in range(N-1):
    if List[i] == List[i+1]:
        count = 'NO'
        
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
List = list(map(int, input().split()))

count = 'YES'
for i in range(N-1):
    for j in range(N-1-i):
        if List[i] == List[i+1+j]:
            count = 'NO'

print(count)

Fixed submission:
N = int(input())
List = list(map(int, input().split()))

List.sort()
count = 'YES'
for i in range(N-1):
    if List[i] == List[i+1]:
        count = 'NO'
        
print(count)
Buggy python submission (verdict: Runtime Error):
H, A = mat(int, input().split())

if H % A == 0:
  print(H / A)
  
elif H % A != 0:
  print(H / A +1)

Fixed submission:
H,A = map(int,input().split())

if H % A != 0:
  print(H//A + 1)
  
elif H % A == 0:
  print(H//A)
Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())

List = []
for _ in N:
  List.append(int(input()))

total = 0
for l in len(List):
  total += List[l]
  
if H > total:
  print('No')
  
elif H <= total:
  print('Yes')


Fixed submission:
H, N = map(int, input().split())
 
List = list(map(int, input().split()))
 
total = 0
for l in range(len(List)):
  total += List[l]
  
if H > total:
  print('No')
  
elif H <= total:
  print('Yes')

Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())

List = map(int, input().split())

total = 0
for l in len(List):
  total += List[l]
  
if H > total:
  print('No')
  
elif H <= total:
  print('Yes')

Fixed submission:
H, N = map(int, input().split())
 
List = list(map(int, input().split()))
 
total = 0
for l in range(len(List)):
  total += List[l]
  
if H > total:
  print('No')
  
elif H <= total:
  print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
ans = [l[0]]

for i in range(n-1):
    l_new = sorted(l[0:i+1])
    if l_new[0] >=l[i+1]:
        ans.append(l[i+1])
        
print(len(ans))

Fixed submission:
n = int(input())
l = list(map(int, input().split()))
Min = l[0]
count = 0

for i in range(n):
    if Min >= l[i]:
        Min = l[i]
        count += 1
        
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
INF = 0

class MaxSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [-INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = max(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] >= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = -INF
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
mxA = max(A)
tree = MaxSegTree(mxA + 10)

for a in A:
    nx = tree.query(max(0, a - K), min(mxA + 1, a + K + 1))
    tree.update(a, nx + 1)

print(tree.query(0, mxA + 1))


Fixed submission:
import sys
input = sys.stdin.buffer.readline
INF = 0

class MaxSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [-INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = max(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] >= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = -INF
        while L < R:
            if R & 1:
                R -= 1
                ret = max(ret, self.data[R - 1])
            if L & 1:
                ret = max(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
mxA = max(A)
tree = MaxSegTree(mxA + 10)

for a in A:
    nx = tree.query(max(0, a - K), min(mxA + 1, a + K + 1))
    tree.update(a, nx + 1)

print(tree.query(0, mxA + 1))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
class Prime:
    def __init__(self, N):
        smallestPrime = [i for i in range(N + 1)]

        for i in range(2, N + 1):
            if smallestPrime[i] != i:
                continue
            for p in range(i * 2, N + 1, i):
                if smallestPrime[p] == p:
                    smallestPrime[p] = i

        self.smallestPrime = smallestPrime

    def isPrime(self, n):
        return n > 1 and self.smallestPrime[n] == n

    def factorization(self, n):
        ret = Counter()
        while n > 1:
            p = self.smallestPrime[n]
            ret[p] += 1
            n //= p
        return ret

N = int(input())
prime = Prime(N + 100)

ans = 0
for c in range(1, N):
    cnt = 1
    for c in prime.factorization(N - c).values():
        cnt *= c + 1
    ans += cnt
print(ans)


Fixed submission:
from collections import Counter
class Prime:
    def __init__(self, N):
        smallestPrime = [i for i in range(N + 1)]

        for i in range(2, N + 1):
            if smallestPrime[i] != i:
                continue
            for p in range(i * 2, N + 1, i):
                if smallestPrime[p] == p:
                    smallestPrime[p] = i

        self.smallestPrime = smallestPrime

    def isPrime(self, n):
        return n > 1 and self.smallestPrime[n] == n

    def factorization(self, n):
        ret = Counter()
        while n > 1:
            p = self.smallestPrime[n]
            ret[p] += 1
            n //= p
        return ret

N = int(input())
prime = Prime(N + 100)

ans = 0
for c in range(1, N):
    cnt = 1
    for c in prime.factorization(N - c).values():
        cnt *= c + 1
    ans += cnt
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N = int(input())
comb = Combination(N + 10)

dis = 0
for i in range(1, N + 1):
    dis += comb.ncr(N, i) * 2 * pow(8, N - i, MOD)
    dis %= MOD
ans = pow(10, N, MOD) - dis - pow(8, N, MOD)
print(ans % MOD)


Fixed submission:
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N = int(input())
comb = Combination(N + 10)

dis = 0
for i in range(1, N + 1):
    dis += comb.ncr(N, i) * 2 * pow(8, N - i, MOD)
    dis %= MOD
ans = pow(10, N, MOD) - dis - pow(8, N, MOD)
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)

    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC >= 0:
        q, K = divmod(K, N)
        ans = q * sumC
    else:
        K = min(K, N)
        1 / 0

    if K == 0:
        return ans

    def calc(now, K):
        ret = -INF
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start, K))

    return ans + mx

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)


Fixed submission:
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC > 0 and K >= N:
        q, K = divmod(K, N)
        K += N
        ans = sumC * (q - 1)
    else:
        K = min(K, N)

    if K == 0:
        return ans

    def calc(now):
        acc = C[now]
        ret = acc
        for _ in range(K - 1):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start))

    return mx + ans

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

def isOk(x):
    cnt = 0
    for a in A:
        cnt += a // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

assert isOk(ok), (ok, isOk(ok))

print(ok)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

def isOk(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

def isOk(x):
    cnt = 0
    for a in A:
        cnt += a // x
    return cnt <= K

ok = max(A)
ng = 0
for _ in range(50):
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

def isOk(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction
from math import ceil, floor

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

def isOk(x):
    cnt = 0
    for a in A:
        cnt += floor(Fraction(a, x))
    return cnt <= K

ok = max(A)
ng = 0
for _ in range(50):
    mid = Fraction(ok + ng, 2)
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ceil(ok))


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

def isOk(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import Fraction
from math import ceil, floor

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

def isOk(x):
    cnt = 0
    for a in A:
        cnt += floor(Fraction(a, x))
    return cnt <= K

ok = max(A)
ng = 0
for _ in range(100):
    mid = Fraction(ok + ng, 2)
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ceil(ok))


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

def isOk(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

def solve():
    ans = []
    N = 26
    for _ in S:
        nx = 0
        res = -10**18
        for i in range(N):
            ans.append(i)
            r = calc(ans)
            ans.pop()
            if res < r:
                nx = i
                res = r
        ans.append(nx)

    return ans

def calc(ans):
    N = 26
    L = [0] * N
    res = 0

    for d, t in enumerate(map(lambda a: a - 1, ans), start=1):
        L[t] = d
        res += S[d - 1][t]
        for c, l in zip(C, L):
            res -= c * (d - l)

    return res

print(*solve(), sep='\n')


Fixed submission:
D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(D)]

for A in S:
    print(A.index(max(A)) + 1)