Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from bisect import bisect
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

x = sum(H) // (A+B*(N-1))
H = sorted(H)
 
while len(H):
    nH = [h - B*x for h in H]
    i = bisect(nH, 0)
    nH = nH[i:]
    H = H[i:]
    if sum([h//D + (h%D>0) for h in nH]) <= x:
        print(x)
        break
    else:
        x = max(x+1, sum(H) // (A+B*(N-1)))

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from bisect import bisect
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

x = sum(H) // (A+B*(N-1))
H = sorted(H)
 
while len(H):
    nH = [h - B*x for h in H]
    i = bisect(nH, 0)
    nH = nH[i:]
    H = H[i:]
    if sum([h//D + (h%D>0) for h in nH]) <= x:
        print(x)
        break
    else:
        x += 1

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from numpy import array, int64
from bisect import bisect
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

x = sum(H) // (A+B*(N-1))
H = array(sorted(H)).astype(int64)
 
while len(H):
    nH = H - B*x
    i = bisect(nH, 0)
    nH = nH[i:]
    H = H[i:]
    if sum(nH//D + (H%D>0)) <= x:
        print(x)
        break
    else:
        x += 1

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

N, A, B = inpl()
D = A-B
H = []
res = 0
for _ in range(N):
    H.append(int(input()))

H = sorted(H)
l = sum(H) // (A+B*(N-1))
r = sum([h//A + (h%A>0) for h in H])

def judge(m):
    nH = [h - B*m for h in H]
    if sum([h//D + (h%D>0) for h in nH if h > 0]) <= m:
        return True
    else:
        return False

while r-l > 1:
    mid = (l+r)//2
    if judge(mid):
        r = mid
    else:
        l = mid
if judge(l):
    print(l)
else:
    print(r)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from bisect import bisect_left, insort
N = int(input())
A = inpl()

before = sorted(A[:N])
after = sorted(A[N:])
x = sum(before)
y = sum(after[:N])
score = x - y

for i in range(N):
    insort(before, A[N+i])
    del after[bisect_left(after, A[N+i])]
    score = max(score, sum(before[-N:]) - sum(after[:N]))

print(score)

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from heapq import heapify, heappop, heappush
from copy import deepcopy

N = int(input())
A = inpl()

before = deepcopy(A[:N])
heapify(before)
middle = A[N:-N]
after = [-a for a in A[-N:]]
heapify(after)

sb = sum(A[:N])
sa = -sum(A[-N:])

SB = [sb]
SA = [sa]

for m in middle:
    b = heappop(before)
    if b < m:
        heappush(before, m)
        sb += m - b
    else:
        heappush(before, b)
    SB.append(sb)    

for m in middle[::-1]:
    m = -m
    a = heappop(after)
    if a < m:
        heappush(after, m)
        sa += m - a
    else:
        heappush(after, a)
    SA.append(sa) 

    
print(max([b+a for b, a in zip(SB, SA[::-1])]))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())

DP1 = [0 for _ in range(W+1)]
DP2 = [0 for _ in range(W+1)]

for w, v in A:
    for i in range(w, W+1):
        DP2[i] = max(DP1[i], DP1[i-w] + v)
    DP1 = deepcopy(DP2)

print(DP1[-1])

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())

DP1 = [0 for _ in range(W+1)]
DP2 = [0 for _ in range(W+1)]

for w, v in A:
    for i in range(w, W+1):
        DP2[i] = max(DP1[i], DP1[i-w] + v)
    DP1 = deepcopy(DP2)

print(DP1[-1])

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from collections import Counter
from itertools import accumulate, product

N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]

for w, v in A:
    B[w-w1].append(v)

B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]

res = 0

for a, b, c, d in product(range(len(C[0])),
                          range(len(C[1])),
                          range(len(C[2])),
                          range(len(C[3]))):
    if w1*a + (w1+1)*b + (w1+2)*c + (w1+3)*d <= W:
        res = max(res, C[0][a] + C[1][b] + C[2][c] + C[3][d])
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

N, M = inpl()

X = inpl()
Y = inpl()

Sx = 0
Sy = 0

for i in range(N-1):
    for j in range(i+1, N):
        Sx += X[j] - X[i]

for i in range(M-1):
    for j in range(i+1, M):
        Sy += Y[j] - Y[i]

print((Sx*Sy)%(10**9+7))

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))

def make(N):
    if N%2:
        L = [N + (N//2)**2 - n**2 + 2*n - 1 for n in range(1, N//2+2)]
        L = L[1::][::-1] + L
        return L
    else:
        L = [N + N*(N-2)//4 -n**2 + n for n in range(1, N//2+1)]
        L = L[::-1] + L
        return L

N, M = inpl()

X = inpl()
Y = inpl()

A = make(N-1)
B = make(M-1)

Sx = 0
Sy = 0

for i, a in enumerate(A):
    Sx += a * (X[i+1] - X[i])

for j, b in enumerate(B):
    Sy += b * (Y[j+1] - Y[j])

print((Sx*Sy)%(10**9 + 7))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy
from operator import add
from itertools import accumulate

N, K = inpl()
A = sorted(inpl())
S = list(accumulate(A, add))
A = A[::-1]
DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from math import ceil

X = int(input())
print(ceil((2*X+1/4)**(1/2) - 1/2))

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, K = inpl()
A = sorted(inpl(), reverse=True)

DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))  

Fixed submission:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from math import ceil

X = int(input())
print(ceil((2*X+1/4)**(1/2) - 1/2))
Buggy python submission (verdict: Runtime Error):
from itertools import combinations, permutations
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = inpl()
    G[a][b] = 1
    G[b][a] = 1

ans = 0
for X in permutations(range(2, N+1)):
    a = 1
    for i in range(N-1):
        b = X[i]
        if G[a][b] == 0:
            break
        a = b
    else:
        ans += 1

print(ans)

Fixed submission:
# -*- coding: utf-8 -*-
A, B = [(int(n)+11)%13 for n in input().split() ]
if A > B:
    print("Alice")
elif A < B:
    print("Bob")
else:
    print("Draw")
Buggy python submission (verdict: Runtime Error):
def inpl(): return list(map(int, input().split()))

N, M = inpl()
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = inpl()
    G[a][b] = 1
    G[b][a] = 1

ans = 0
for X in permutations(range(2, N+1)):
    a = 1
    for i in range(N-1):
        b = X[i]
        if G[a][b] == 0:
            break
        a = b
    else:
        ans += 1

print(ans)

Fixed submission:
# -*- coding: utf-8 -*-
from queue import Queue

q = Queue()
N, M = [int(n) for n in input().split()]
graph = {n:[] for n in range(1, N+1)}

for m in range(M):
    a, b = [int(n) for n in input().split()]
    graph[a].append(b)
    graph[b].append(a)

end = 0
for n in range(2, N+1):
    if len(graph[n]) == 1:
        end = n

ok = []
q.put([1, []])

while not q.empty():
    point, past = q.get()
    for d in graph[point]:
        if not d in past:
            if len(past + [point, d]) == N:
                ok.append(past + [point, d])
            else:
                q.put([d, past+[point]])

print(len(ok))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(100000)
N = int(input())
C = [[] for _ in range(N)]

for i in range(1, N):
    C[int(input())-1].append(i)

def cal(x):
    if len(C[x]) == 0:
        return 0
    else:
        D = sorted([cal(a) for a in C[x]], reverse=True)
        res = 0
        for i, d in enumerate(D, start=1):
            res = max(res, i+d)
        return res

print(cal(0))

Fixed submission:
# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(10000000)

N = int(input())
C = [[] for _ in range(N+1)]

for i in range(1, N):
    C[int(input())-1].append(i)

def cal(x):
    if len(C[x]) == 0:
        return 0
    else:
        D = sorted([cal(a) for a in C[x]], reverse=True)
        res = 0
        for i, d in enumerate(D, start=1):
            res = max(res, i+d)
        return res

print(cal(0))

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
N = int(input())
C = [[] for _ in range(N)]

for i in range(1, N):
    C[int(input())-1].append(i)

def cal(x):
    if len(C[x]) == 0:
        return 0
    else:
        D = sorted([cal(a) for a in C[x]], reverse=True)
        res = 0
        for i, d in enumerate(D, start=1):
            res = max(res, i+d)
        return res

print(cal(0))

Fixed submission:
# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(10000000)

N = int(input())
C = [[] for _ in range(N+1)]

for i in range(1, N):
    C[int(input())-1].append(i)

def cal(x):
    if len(C[x]) == 0:
        return 0
    else:
        D = sorted([cal(a) for a in C[x]], reverse=True)
        res = 0
        for i, d in enumerate(D, start=1):
            res = max(res, i+d)
        return res

print(cal(0))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
from itertools import combinations
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] # [next, rank]

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: # rank is same
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

res = [1 for _ in range(N+1)]

for x, y in combinations(range(1, N+1), 2):
    if find(x, 0) == find(y, 0) and find(x, 1) == find(y, 1):
        res[x] += 1
        res[y] += 1

print(" ".join(map(str, res[1:])))

Fixed submission:
# -*- coding: utf-8 -*-
from itertools import combinations
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] # [next, rank]

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: # rank is same
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

D = defaultdict(lambda: 0)
P = []
for i in range(1, N+1):
    a, b = find(i, 0), find(i, 1)
    D[(a, b)] += 1
    P.append((a, b))
print(" ".join(map(str, [D[(a, b)] for a, b in P])))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
def inpl(): return map(int, input().split())

sx, sy, tx, ty = inpl()
N = int(input())
X = np.zeros((1, N+2), dtype=np.float64)
Y = np.zeros((1, N+2), dtype=np.float64)
R = np.zeros((1, N+2), dtype=np.float64)

X[0][0] = sx
Y[0][0] = sy
X[0][N+1] = tx
Y[0][N+1] = ty

for i in range(N):
    X[0][i+1], Y[0][i+1], R[0][i+1] = inpl()

G = np.maximum(np.sqrt(np.square(X-X.T) + np.square(Y-Y.T)) - (R+R.T),
               np.zeros((N+2, N+2), dtype=np.float64))
Gsp = csgraph_from_dense(G, null_value=np.inf)

print(dijkstra(Gsp, indices=0)[-1])


Fixed submission:
# -*- coding: utf-8 -*-
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
def inpl(): return map(int, input().split())

sx, sy, tx, ty = inpl()
N = int(input())
X = np.zeros((1, N+2), dtype=np.float64)
Y = np.zeros((1, N+2), dtype=np.float64)
R = np.zeros((1, N+2), dtype=np.float64)

X[0][0] = sx
Y[0][0] = sy
X[0][N+1] = tx
Y[0][N+1] = ty

for i in range(N):
    X[0][i+1], Y[0][i+1], R[0][i+1] = inpl()

G = np.maximum(np.sqrt(np.square(X-X.T) + np.square(Y-Y.T)) - (R+R.T),
               np.zeros((N+2, N+2), dtype=np.float64)) 
G += np.diag(np.ones(N+2, dtype=np.float64)*np.inf)
G = csgraph_from_dense(G, null_value=np.inf)
print(dijkstra(G, indices=0)[-1])
Buggy python submission (verdict: Runtime Error):
from random import shuffle
from collections import Counter
def inpl(): return list(map(int, input().split()))

#N = 20000
#P = list(range(1, N+1))
#shuffle(P)

N = int(input())
P = inpl()

A = [0]*N
B = [0]*N
S = [10**9 - N] * (N)
for i, p in enumerate(P):
    S[p-1] += i

A[0] = 1
B[0] = S[0] - 1

for i in range(1, N):
    A[i] = max(A[i-1] + 1, S[i] - B[i-1] + 1)
    B[i] = S[i] - A[i]

for i in range(N-1):
    assert A[i] < A[i+1]
    assert B[i] > B[i+1]

assert B[-1] > 0
print(*A)
print(*B)


Fixed submission:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = []
for _ in range(H):
    A.append([x=="#" for x in input()] + [False])

A.append([False] * (W+1))

Q = [[0, 0]]
visited = [[False]*(W+1) for _ in range(H+1)]
visited[0][0] = True

while Q:
    h, w = Q.pop()
    for dh, dw in [[0, 1], [1, 0]]:
        nh, nw = h+dh, w+dw
        if A[nh][nw] and not visited[nh][nw]:
            visited[nh][nw] = True
            Q.append([nh, nw])

plength = sum([sum(a) for a in A])

if plength == (H+W-1) and visited[H-1][W-1]:
    print("Possible")
else:
    print("Impossible")

Buggy python submission (verdict: Runtime Error):
from random import shuffle
from collections import Counter
def inpl(): return list(map(int, input().split()))

#N = 20000
#P = list(range(1, N+1))
#shuffle(P)

N = int(input())
P = inpl()

A = [0]*N
B = [0]*N
S = [10**9 - N] * (N)
for i, p in enumerate(P):
    S[p-1] += i

A[0] = 1
B[0] = S[0] - 1

for i in range(1, N):
    A[i] = max(A[i-1] + 1, S[i] - B[i-1] + 1)
    B[i] = S[i] - A[i]

for i in range(N-1):
    assert A[i] < A[i+1]
    assert B[i] > B[i+1]

assert B[-1] > 0
print(*A)
print(*B)

Fixed submission:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = []
for _ in range(H):
    A.append([x=="#" for x in input()] + [False])

A.append([False] * (W+1))

Q = [[0, 0]]
visited = [[False]*(W+1) for _ in range(H+1)]
visited[0][0] = True

while Q:
    h, w = Q.pop()
    for dh, dw in [[0, 1], [1, 0]]:
        nh, nw = h+dh, w+dw
        if A[nh][nw] and not visited[nh][nw]:
            visited[nh][nw] = True
            Q.append([nh, nw])

plength = sum([sum(a) for a in A])

if plength == (H+W-1) and visited[H-1][W-1]:
    print("Possible")
else:
    print("Impossible")
Buggy python submission (verdict: Runtime Error):
def inpl(): return list(map(int, input().split()))

W, H, N = inpl()
l, r, d, u = 0, W, 0, H

for _ in range(N):
    x, y, a = inpl()
    if a == 0:
        l = max(l, a)
    elif a == 1:
        r = min(r, a)
    elif a == 2:
        d = max(d, a)
    else:
        assert a == 3
        u = min(u, a)
print((r-l)*(u-d))

Fixed submission:
def inpl(): return list(map(int, input().split()))

W, H, N = inpl()
l, r, d, u = 0, W, 0, H

for _ in range(N):
    x, y, a = inpl()
    if a == 1:
        l = max(l, x)
    elif a == 2:
        r = min(r, x)
    elif a == 3:
        d = max(d, y)
    else:
        assert a == 4
        u = min(u, y)
print(max((r-l), 0)*max((u-d), 0))
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt, factorial
from sys import setrecursionlimit
setrecursionlimit(100000)

def inpl(): return list(map(int, input().split()))
N = int(input())
S = int(input())

RN = int(sqrt(N))
RN += ((RN+1)**2 == N)

def func(b, N):
    if b == 0:
        return -1
    tmp = 0
    while N:
        N, d = divmod(N, b)
        tmp += d
    return tmp

for b in range(2, RN+1):
    tmp = func(b, N)
    if tmp == S:
        print(b)
        break
else:
    for x in range(RN, 0, -1):
        num = (N-S+x)//x
        b = num//x
        if func(b, N) == S:
            print(b)
            break
    else:
        print(-1)

Fixed submission:
# -*- coding: utf-8 -*-
from math import sqrt
n = int(input())
s = int(input())

def f(b, n):
    ans = 0
    while n >= b:
        ans += n%b
        n = n//b
    return ans + n

if n==s:
    print(n+1)
    exit()

for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        break
else:
    for p in range(1, int(sqrt(n))+1)[::-1]:
        d, m = divmod(p+n-s, p)
        if m == 0 and d >= 2 and f(d, n) == s:
            print(d)
            break
    else:
        print(-1)

Buggy python submission (verdict: Runtime Error):
from math import sqrt, factorial
from sys import setrecursionlimit
setrecursionlimit(100000)

def inpl(): return list(map(int, input().split()))
N = int(input())
S = int(input())

RN = int(sqrt(N))
RN += ((RN+1)**2 == N)

def func(b, N):
    tmp = 0
    while N:
        N, d = divmod(N, b)
        tmp += d
    return tmp

for b in range(2, RN+1):
    tmp = func(b, N)
    if tmp == S:
        print(b)
        break
else:
    for x in range(1, RN+1):
        num = N-S+x
        if num%x:
            continue
        b = num//x
        if N//b + N%b == S:
            print(b)
            break
    else:
        print(-1)

Fixed submission:
# -*- coding: utf-8 -*-
from math import sqrt
n = int(input())
s = int(input())

def f(b, n):
    ans = 0
    while n >= b:
        ans += n%b
        n = n//b
    return ans + n

if n==s:
    print(n+1)
    exit()

for b in range(2, int(sqrt(n))+1):
    if f(b, n) == s:
        print(b)
        break
else:
    for p in range(1, int(sqrt(n))+1)[::-1]:
        d, m = divmod(p+n-s, p)
        if m == 0 and d >= 2 and f(d, n) == s:
            print(d)
            break
    else:
        print(-1)
Buggy python submission (verdict: Runtime Error):
N = int(input())
a_lis = list(input().split())

# 10^18を超えたら駄目

ans=1
rough_power=0
for i in a_lis:
    rough_power+=len(i)-1

if rough_power>18:
    print("-1")
elif 0 in a_lis:
    print(0)
else:
    for j in a_lis:
        ans=ans*int(j)

    if ans>pow(10,18):
        print("-1")
    else:
        print(ans)

Fixed submission:
x,y = map(int, input().split())
ans = x*y
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a_lis = list(input().split())

# 10^18を超えたら駄目

ans=1

for j in a_lis:
    ans=ans*int(j)

if ans>pow(10,18):
    print("-1")
else:
    print(ans)

Fixed submission:
n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)