Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
src = list(map(int,input().split()))
es = [tuple(map(int,input().split())) for i in range(M)]

if N == 1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    root(i)
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)


Fixed submission:
X,Y = map(int,input().split())
if X%Y == 0:
    print(-1)
else:
    print(X)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
def q(i):
    print(i)
    r = input()
    if r[0]=='V': exit()
    return r[0]

X = q(0)
def is_ok(m):
    if m==N: return False
    return q(m)==X
ok = 0
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

Fixed submission:
N = int(input())

q = 0
res = []
for i in range(20):
    print(q)
    s = input()
    if s[0] == 'V':
        exit()
    res.append((q,s[0]))
    res.sort()
    if len(res) == 1:
        q = N//2
        continue
    for (i1,g1),(i2,g2) in zip(res,res[1:]):
        if i2-i1 == 1: continue
        if (i2-i1)%2 == int(g1==g2):
            q = (i2+i1)//2
            break
    else:
        q = (res[-1][0] + N + 1)//2

Buggy python submission (verdict: Runtime Error):
N = int(input())

q = 0
res = []
for i in range(20):
    print(q)
    s = input()
    if s[0] == 'V':
        exit()
    res.append((q,s[0]))
    if len(res) == 1:
        q = N//2
        continue
    for (i1,g1),(i2,g2) in zip(res,res[1:]):
        if (i2-i1)%2 == int(g1==g2):
            q = (i2-i1)//2
            break
    else:
        q = (res[-1][0] + N + 1)//2

    print(res)


Fixed submission:
N = int(input())

q = 0
res = []
for i in range(20):
    print(q)
    s = input()
    if s[0] == 'V':
        exit()
    res.append((q,s[0]))
    res.sort()
    if len(res) == 1:
        q = N//2
        continue
    for (i1,g1),(i2,g2) in zip(res,res[1:]):
        if i2-i1 == 1: continue
        if (i2-i1)%2 == int(g1==g2):
            q = (i2+i1)//2
            break
    else:
        q = (res[-1][0] + N + 1)//2
Buggy python submission (verdict: Runtime Error):
n = input()
print(48-n)

Fixed submission:
M = int(input())
print(48-M)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
center_i = N//2
center = S[center_i]

ans = N//2 + N%2
if N%2==0 and center != S[center_i+1]:
    print(ans)
    exit()
l = center_i - 1
r = center_i + 1 + (N%2==0)
while l >= 0:
    if not (S[l] == center == S[r]):
        break
    l -= 1
    r += 1
    ans += 1
print(ans)

Fixed submission:
S = input()
N = len(S)
center_i = N//2
center = S[center_i]

ans = N//2
l = r = center_i
if N%2==0:
    l -= 1
while l >= 0:
    if not (S[l] == center == S[r]):
        break
    l -= 1
    r += 1
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)

ans = N//2
l = r = N//2
if N%2 == 0: r += 1

while l >= 0:
    if S[l] == '1' or S[r] == '1':
        break
    l -= 1
    r += 1
    ans += 1
print(max(ans, N//2 + N%2))

Fixed submission:
S = input()
N = len(S)

m = N//2
if N%2 == 0:
    if S[m] != S[m-1]:
        print(m)
        exit()
    ans = m+1
    for i in range(1,m):
        if S[m] == S[m+i] == S[m-1-i]:
            ans += 1
        else:
            break
else:
    ans = m+1
    for i in range(1,m+1):
        if S[m] == S[m+i] == S[m-i]:
            ans += 1
        else:
            break
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = 0
n = N
while n >= 10:
    a += n%10
    n //= 10
print('Yes' if N % a == 0 else 'No')


Fixed submission:
N = int(input())
a = 0
n = N
while n >= 1:
    a += n%10
    n //= 10
print('Yes' if N % a == 0 else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
VW = [tuple(map(int,input().split())) for i in range(Q)]

ans = []
for v,w in VW:
    while v != w:
        if v > w: v,w = w,v
        w = (w+N-2)//N
    ans.append(v)
print(*ans, sep='\n')

Fixed submission:
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

src = [tuple(map(int,input().split())) for i in range(Q)]
for a,b in src:
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    print(a)


Fixed submission:
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

for i in range(Q):
    a,b = map(int,input().split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    print(a)


Fixed submission:
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import sys
N,Q = map(int,raw_input().split())
if N == 1:
  for i in range(Q):
    a,b = map(int,raw_input().split())
    print(min(a,b))
  sys.exit()

MAXN = 10**9
borders = [1]
while borders[-1] < MAXN:
  borders.append(borders[-1] + N**(len(borders) - 1))

def pos(a):
  rank = bisect.bisect_right(borders, a) - 1
  idx = a - borders[rank]
  return (rank,idx)

def parent(p):
  rank,idx = p
  return (rank-1, idx//N)

for i in range(Q):
  a,b = map(int,raw_input().split())
  p1,p2 = pos(a),pos(b)
  while p1 != p2:
    if p1 > p2:
      p1 = parent(p1)
    else:
      p2 = parent(p2)
  rank,idx = p1
  print(borders[rank] + idx) 

Fixed submission:
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,raw_input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

a = b = 0
visited = [0 for i in range(N)]
stack = [0]
while stack:
  fr = stack.pop()
  if not visited[fr]:
    visited[fr] = 1
    a += 1
  for to in es[fr]:
    if visited[to]: continue
    stack.append(to)

stack = [1]
while stack:
  fr = stack.pop()
  if not visited[fr]:
    visited[fr] = 1
    b += 1
  for to in es[fr]:
    if visited[to]: continue
    stack.append(to)

if a > b: a,b = b,a
unused = N-a-b
b += unused

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)

Fixed submission:
from collections import deque
N,M = map(int,input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(lambda x:int(x)-1,input().split())
  es[a].append(b)
  es[b].append(a)

a = b = 1
visited = [1,1] + [0]*(N-2)
q = deque([0])
while q:
  fr = q.popleft()
  for to in es[fr]:
    if visited[to]: continue
    q.append(to)
    visited[to] = 1
    a += 1

q = deque([1])
while q:
  fr = q.popleft()
  for to in es[fr]:
    if visited[to]: continue
    q.append(to)
    visited[to] = 1
    b += 1

if a > b: a,b = b,a
unused = N-a-b
b += unused

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N,M = map(int,raw_input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

group = [0 for i in range(N)]
stack = [0]
while stack:
  fr = stack.pop()
  group[fr] = 1
  for to in es[fr]:
    if group[to] > 0: continue
    stack.append(to)

stack = [1]
while stack:
  fr = stack.pop()
  group[fr] = 2
  for to in es[fr]:
    if group[to] > 0: continue
    stack.append(to)

ctr = Counter(group)
a = ctr[1]
b = ctr[2]
if a > b: a,b = b,a
b += ctr[0]

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)

Fixed submission:
from collections import deque
N,M = map(int,input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(lambda x:int(x)-1,input().split())
  es[a].append(b)
  es[b].append(a)

a = b = 1
visited = [1,1] + [0]*(N-2)
q = deque([0])
while q:
  fr = q.popleft()
  for to in es[fr]:
    if visited[to]: continue
    q.append(to)
    visited[to] = 1
    a += 1

q = deque([1])
while q:
  fr = q.popleft()
  for to in es[fr]:
    if visited[to]: continue
    q.append(to)
    visited[to] = 1
    b += 1

if a > b: a,b = b,a
unused = N-a-b
b += unused

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
HP = [tuple(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: sum(x))

INF = float('inf')
dp = [[INF]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
maxj = 0
for i,(h,p) in enumerate(HP):
	for j in range(maxj,-1,-1):
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
		if dp[i][j] <= h:
			dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + p)
			if j == maxj:
				maxj += 1
print(maxj)

Fixed submission:
N = int(input())
HP = [tuple(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: sum(x))

INF = float('inf')
dp = [0]
maxj = 0
for i,(h,p) in enumerate(HP):
	dp2 = [INF] * (maxj + 2)
	for j in range(maxj,-1,-1):
		dp2[j] = min(dp2[j], dp[j])
		if dp[j] <= h:
			dp2[j+1] = min(dp2[j+1], dp[j] + p)
			if j == maxj:
				maxj += 1
	dp = dp2
print(maxj)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ts = list(map(int,input().split()))
vs = list(map(int,input().split()))

durs = [0]
for i in range(N):
    durs.append(durs[-1] + ts[i])
T = durs[-1]

maxv = [0.5*i for i in range(T)] + [0.5*i for i in range(T,-1,-1)]

for i in range(N):
    t1,t2 = durs[i],durs[i+1]
    for ti in range(2*T + 1):
        t = ti*0.5
        if t < t1:
            maxv[ti] = min(maxv[ti], vs[i] + (t1-t))
        elif t > t2:
            maxv[ti] = min(maxv[ti], vs[i] + (t-t2))
        else:
            maxv[ti] = min(maxv[ti], vs[i])

ans = 0.0
for i in range(2*T):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)


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

maxv = [0]
for v,t in zip(vs,ts):
    maxv[-1] = min(maxv[-1], v)
    for ti in range(t*2):
        maxv.append(v)
T = len(maxv)

for i in range(T-1):
    maxv[i+1] = min(maxv[i+1], maxv[i] + 0.5)

maxv[-1] = 0
for i in reversed(range(T-1)):
    maxv[i] = min(maxv[i], maxv[i+1] + 0.5)

ans = 0.0
for i in range(T-1):
    ans += (maxv[i] + maxv[i+1]) * 0.25
print(ans)
Buggy python submission (verdict: Runtime Error):
H,W = map(int,input().split())
src = [input() for i in range(H)]

ans = []
for row in src:
    ans.append(list(row))

dxy = [(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(-1,0)]
for y in range(H):
    for x in range(W):
        if src[y][x] == '#': continues
        c = 0
        for dx,dy in dxy:
            if x+dx <= 0 or x+dx >= W or y+dy <= 0 or y+dy >= H: continue
            if src[y+dy][x+dx] == '#': c += 1        
        ans[i][j] = c

for row in ans:
    print(''.join(list(map(str,row))))


Fixed submission:
H,W = map(int,input().split())
src = [input() for i in range(H)]

ans = []
for row in src:
    ans.append(list(row))

for i in range(H):
    for j in range(W):
        if src[i][j] == '#': continue
        c = 0
        if i > 0:
            if j > 0 and src[i-1][j-1] == '#': c += 1
            if src[i-1][j] == '#': c += 1
            if j < W-1 and src[i-1][j+1] == '#': c += 1
        if j > 0 and src[i][j-1] == '#': c += 1
        if j < W-1 and src[i][j+1] == '#': c += 1
        if i < H-1:
            if j > 0 and src[i+1][j-1] == '#': c += 1
            if src[i+1][j] == '#': c += 1
            if j < W-1 and src[i+1][j+1] == '#': c += 1
        ans[i][j] = c

for row in ans:
    print(''.join(list(map(str,row))))

Buggy python submission (verdict: Runtime Error):
H,W = map(int,input().split())
src = [input() for i in range(H)]

ans = []
for row in src:
    ans.append(list(row))

dxy = [(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(-1,0)]
for y in range(H):
    for x in range(W):
        if src[y][x] == '#': continues
        c = 0
        for dx,dy in dxy:
            if x+dx <= 0 or x+dx >= W or y+dy <= 0 or y+dy >= H: continue
            if src[y+dy][x+dx] == '#': c += 1        
        ans[i][j] = c

for row in ans:
    print(''.join(list(map(str,row))))


Fixed submission:
H,W = map(int,input().split())
src = [input() for i in range(H)]

ans = []
for row in src:
    ans.append(list(row))

for i in range(H):
    for j in range(W):
        if src[i][j] == '#': continue
        c = 0
        if i > 0:
            if j > 0 and src[i-1][j-1] == '#': c += 1
            if src[i-1][j] == '#': c += 1
            if j < W-1 and src[i-1][j+1] == '#': c += 1
        if j > 0 and src[i][j-1] == '#': c += 1
        if j < W-1 and src[i][j+1] == '#': c += 1
        if i < H-1:
            if j > 0 and src[i+1][j-1] == '#': c += 1
            if src[i+1][j] == '#': c += 1
            if j < W-1 and src[i+1][j+1] == '#': c += 1
        ans[i][j] = c

for row in ans:
    print(''.join(list(map(str,row))))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(N)]
xs = []
ys = []
for x,y in XY:
    xs.append(x)
    ys.append(y)
xs.sort()
ys.sort()

def is_ok(l,r,d,u):
    k = 0
    for x,y in XY:
        if l <= x <= r and d <= y <= u:
            k += 1
            if k >= K:
                return True
    return False

ans = float('inf')
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N-1):
            for l in range(k+1,N):
                l,r,d,u = xs[i],xs[j],ys[k],ys[l]
                if (r-l)*(u-d) >= ans: continue
                if is_ok(l,r,d,u):
                    ans = (r-l)*(u-d)
print(ans)

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

xs = []
ys = []
for i in range(N):
    x,y = map(int,input().split())
    xs.append((x,y,i))
    ys.append((y,x,i))
xs.sort()
ys.sort()

x_order = {}
for xo,p in enumerate(xs):
    x,y,i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y,x,pi = ys[i]
    xo = x_order[pi]
    for j in range(N+1):
        cums[i+1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')
for x1 in range(N-1):
    for x2 in range(x1+1,N):
        for y1 in range(N-1):
            for y2 in range(y1+1,N):
                if cums[y2+1][x2+1] - cums[y2+1][x1] - cums[y1][x2+1] + cums[y1][x1] < K:
                    continue
                area = (xs[x2][0] - xs[x1][0]) * (ys[y2][0] - ys[y1][0])
                ans = min(ans, area)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
  stack = [(0,1)]
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in es[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to, -color))
  return True

if is_bipartite():
  b = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for to in es[v]:
    if colors[to] == color:
      return False
    if colors[to] == 0 and not dfs(to, -color):
      return False
  return True

def is_bipartite():
  return dfs(0,1)

if is_bipartite():
  b = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)

Buggy python submission (verdict: Runtime Error):
N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for to in es[v]:
    if colors[to] == color:
      return False
    if colors[to] == 0 and not dfs(to, -color):
      return False
  return True

def is_bipartite():
  return dfs(0,1)

if is_bipartite():
  b = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for to in es[v]:
    if colors[to] == color:
      return False
    if colors[to] == 0 and not dfs(to, -color):
      return False
  return True

def is_bipartite():
  return dfs(0,1)

if is_bipartite():
  b = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)
Buggy python submission (verdict: Runtime Error):
A,B,C,D,E,F = map(int,input().split())

waters = set()
for w1 in range(0,F+1,B):
    if w1*100 > F: break
    for w2 in range(0,F+1,A):
        w = (w1+w2)*100
        if w > F: break
        if w==0: continue
        waters.add(w)

sugars = set()
for s1 in range(0,F+1,D):
    if s1 > F: break
    for s2 in range(0,F+1,C):
        s = s1+s2
        if s > F: break
        sugars.add(s)

ans_r = 0
ans_s = ans_w = None
for w in sorted(waters):
    if w > F: break
    for s in sorted(sugars):
        if w+s > F: break
        if s*100 > w*E: break
        r = 100*s/(s+w)
        if r > ans_r:
            ans_r = r
            ans_w = w
            ans_s = s
print(ans_s+ans_w, ans_s)

Fixed submission:
A,B,C,D,E,F = map(int, input().split())

ws = set()
i = j = 0
while True:
    j = 0
    if B*i > F//100: break
    while True:
        w = B*i + A*j
        if w > F//100: break
        ws.add(w)
        j += 1
    i += 1
ws = list(ws)
ws.sort()

ss = set()
i = j = 0
while True:
    j = 0
    if D*i > F: break
    while True:
        s = D*i + C*j
        if s > F: break
        ss.add(s)
        j += 1
    i += 1
ss = list(ss)
ss.sort()

limit = E / (100+E)
water = A*100
sugar = rate = 0
for w in ws:
    w = w*100
    if w == 0: continue
    if w > F: break
    for s in ss:
        if w+s > F: break
        r = s / (w+s)
        if r > limit: break
        if r > rate:
            rate = r
            water = w
            sugar = s
print(water+sugar, sugar)

Buggy python submission (verdict: Runtime Error):
A,B,C,D,E,F = map(int,input().split())

waters = set()
for w1 in range(0,F+1,B):
    if w1*100 > F: break
    for w2 in range(0,F+1,A):
        w = (w1+w2)*100
        if w > F: break
        waters.add(w)

sugars = set()
for s1 in range(0,F+1,D):
    if s1 > F: break
    for s2 in range(0,F+1,C):
        s = s1+s2
        if s > F: break
        if s==0: continue
        sugars.add(s)

ans_r = 0
ans_s = ans_w = None
for w in sorted(waters):
    if w > F: break
    for s in sorted(sugars):
        if w+s > F: break
        if s*100 > w*E: break
        r = 100*s/(s+w)
        if r > ans_r:
            ans_r = r
            ans_w = w
            ans_s = s
print(ans_s+ans_w, ans_s)

Fixed submission:
A,B,C,D,E,F = map(int, input().split())

ws = set()
i = j = 0
while True:
    j = 0
    if B*i > F//100: break
    while True:
        w = B*i + A*j
        if w > F//100: break
        ws.add(w)
        j += 1
    i += 1
ws = list(ws)
ws.sort()

ss = set()
i = j = 0
while True:
    j = 0
    if D*i > F: break
    while True:
        s = D*i + C*j
        if s > F: break
        ss.add(s)
        j += 1
    i += 1
ss = list(ss)
ss.sort()

limit = E / (100+E)
water = A*100
sugar = rate = 0
for w in ws:
    w = w*100
    if w == 0: continue
    if w > F: break
    for s in ss:
        if w+s > F: break
        r = s / (w+s)
        if r > limit: break
        if r > rate:
            rate = r
            water = w
            sugar = s
print(water+sugar, sugar)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N,M,R = map(int,input().split())
towns = list(map(int,input().split()))
INF = 200000
cs =[[INF for j in range(N)] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1, b-1
    cs[a][b] = c
    cs[b][a] = c
for i in range(N):
    cs[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])

ans = INF * N
for ptn in itertools.permutations(towns):
    tmp = 0
    for i in range(len(ptn)-1):
        tmp += cs[ptn[i]-1][ptn[i+1]-1]
    ans = min(ans, tmp)
print(ans)


Fixed submission:
import itertools
N,M,R = map(int,input().split())
towns = list(map(lambda x:int(x)-1,input().split()))
INF = float('inf')
es = [[INF]*N for i in range(N)]
for i in range(N):
    es[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    es[a][b] = es[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            es[i][j] = min(es[i][j], es[i][k] + es[k][j])

ans = INF
for ptn in itertools.permutations(range(R)):
    tmp = 0
    for a,b in zip(ptn, ptn[1:]):
        t1,t2 = towns[a],towns[b]
        tmp += es[t1][t2]
    ans = min(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
INF = N+1
nex = [[INF]*26 for _ in range(N+1)]
for i,c in enumerate(S[::-1]):
    ic = ord(c) - ord('a')
    for j in range(26):
        nex[N-i-1][j] = N-i-1 if j==ic else nex[N-i][j]

dp = [N] * (N+3)
dp[INF] = dp[INF+1] = 0
for i in range(N,-1,-1):
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[nex[i][j]+1]+1)
        if tmp == 1: break
    dp[i] = tmp

ans = []
i = 0
for v in range(dp[0]-1,-1,-1):
    for j in range(26):
        if dp[nex[i][j]+1] != v: continue
        ans.append(chr(j + ord('a')))
        i = nex[i][j]+1
        break

print(''.join(ans))

Fixed submission:
S = input()
N = len(S)
INF = N+1
nex = [[INF]*26 for _ in range(N+1)]
for i,c in enumerate(S[::-1]):
    ic = ord(c) - ord('a')
    for j in range(26):
        nex[N-i-1][j] = N-i-1 if j==ic else nex[N-i][j]

dp = [N] * (N+3)
dp[INF] = dp[INF+1] = 0
for i in range(N,-1,-1):
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[nex[i][j]+1]+1)
        if tmp == 1: break
    dp[i] = tmp

ans = []
i = 0
for v in range(dp[0]-1,-1,-1):
    for j in range(26):
        if dp[nex[i][j]+1] != v: continue
        ans.append(chr(j + ord('a')))
        i = nex[i][j]+1
        break

print(''.join(ans))