Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
while True:
    n = input()
    if n == '0000': break
    if len(n) < 4: n = n.zfill(4)
    if reduce(lambda x,y: x and y, [n[0] == s for s in n]):
        print('NA')
    else:
        cnt = 0
        while n != '6174':
            s = ''.join(sorted(n))
            l = s[::-1]
            n = str(int(l)-int(s))
            if len(n) < 4: n.zfill(4)
            cnt += 1
        print(cnt)

Fixed submission:
from functools import reduce
while True:
    n = input()
    if n == '0000': break
    if len(n) < 4: n = n.zfill(4)
    if reduce(lambda x,y: x and y, [n[0] == s for s in n]):
        print('NA')
    else:
        cnt = 0
        while n != '6174':
            s = ''.join(sorted(n))
            l = s[::-1]
            n = str(int(l)-int(s))
            if len(n) < 4: n = n.zfill(4)
            cnt += 1
        print(cnt)
Buggy python submission (verdict: Runtime Error):
board = [[False]*1000001]*1000001
while True:
    m = int(input())
    if m == 0: break
    sx, sy = map(int, input().split())
    star = []
    for i in range(m-1):
        x, y = map(int, input().split())
        star.append((x-sx, y-sy))
    
    
    n = int(input())
    starlist = [tuple(map(int, input().split())) for i in range(n)]
    for i in range(n):
        board[starlist[i][0]][starlist[i][1]] = True
    for i in range(n):
        flag = True
        for j in range(len(star)):
            dx = starlist[i][0] + star[j][0]
            dy = starlist[i][1] + star[j][1]
            if board[dx][dy] == False:
                flag = False
                break
        if flag == True:
            print("{} {}".format(str(starlist[i][0] - sx), str(starlist[i][1] -sy)))
            break
    

Fixed submission:
while True:
    m = int(input())
    if m == 0: break
    star = list({tuple(map(int, input().split())) for i in range(m)})
    sx, sy = star[0]
    
    n = int(input())
    starset = {tuple(map(int, input().split())) for i in range(n)}
    for x, y in starset:
        flag = True
        for j in range(len(star)-1):
            dx = x + star[j+1][0] - sx
            dy = y + star[j+1][1] - sy
            if (dx, dy) not in starset:
                flag = False
                break

        if flag == True:
            print(x - sx, y - sy)
            break
Buggy python submission (verdict: Time Limit Exceeded):
drc = [(0, 1), (1, 0)]


def dfs(r, c):
    ret = []
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if nr < H and nc < W and board[nr][nc].isdigit():
            cand = dfs(nr, nc)
            if len(cand) > len(ret) or (len(cand) == len(ret) and cand > ret):
                ret = cand
    return [board[r][c]] + ret


while True:
    W, H = map(int, input().split())
    if not (W | H):
        break
    board = [input() for _ in range(H)]
    ans = ''
    for r in range(H):
        for c in range(W):
            if board[r][c].isdigit() and board[r][c] != '0':
                cand = ''.join(dfs(r, c))
                # print(cand)
                if len(cand) > len(ans) or (len(cand) == len(ans) and cand > ans):
                    ans = cand
    print(ans)

Fixed submission:
drc = [(0, 1), (1, 0)]


def dfs(r, c):
    if (r, c) in memo:
        return memo[r, c]
    ret = ''
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if nr < H and nc < W and board[nr][nc].isdigit():
            cand = dfs(nr, nc)
            if len(cand) > len(ret) or (len(cand) == len(ret) and cand > ret):
                ret = cand
    memo[r, c] = board[r][c] + ''.join(ret)
    return board[r][c] + ret


while True:
    W, H = map(int, input().split())
    if not (W | H):
        break
    board = [input() for _ in range(H)]
    memo = dict()
    ans = ''
    for r in range(H):
        for c in range(W):
            if board[r][c].isdigit() and board[r][c] != '0':
                cand = dfs(r, c)
                if len(cand) > len(ans) or (len(cand) == len(ans) and cand > ans):
                    ans = cand
    print(ans)
Buggy python submission (verdict: Runtime Error):
def cut(d, w, s):
    s %= 2 * (d + w)
    sq = []
    if 0 < s < w:
        sq = [(d, s), (d, w - s)]
    elif w < s < w + d:
        s -= w
        sq = [(s, w), (d - s, w)]
    elif w + d < s < 2 * w + d:
        s -= w + d
        sq = [(d, s), (d, w - s)]
    elif 2 * w + d < s < 2 * (w + d):
        s -= 2 * w + d
        sq = [(s, w), (d - s, w)]
    else:
        assert(False)
    p1, p2 = sq
    if p1[0] * p1[1] > p2[0] * p2[1]:
        p1, p2 = p2, p1
    return p1, p2


while True:
    N, W, D = map(int, input().split())
    if not (N | W | D):
        break
    square = [(D, W)]
    for _ in range(N):
        p, s = map(int, input().split())
        square[p - 1], p1 = cut(*square[p - 1], s)
        square.append(p1)
    print(*sorted(d * w for d, w in square))

Fixed submission:
def cut(d, w, s):
    s %= d + w
    if 0 < s < w:
        p1, p2 = (d, s), (d, w - s)
    else:
        s -= w
        p1, p2 = (s, w), (d - s, w)
    if p1[0] * p1[1] > p2[0] * p2[1]:
        p1, p2 = p2, p1
    return [p1, p2]


while True:
    N, W, D = map(int, input().split())
    if not (N | W | D):
        break
    square = [(D, W)]
    for _ in range(N):
        p, s = map(int, input().split())
        d, w = square.pop(p - 1)
        square.extend(cut(d, w, s))
    print(*sorted(d * w for d, w in square))

Buggy python submission (verdict: Runtime Error):
def cut(d, w, s):
    s %= 2 * (d + w)
    sq = []
    if 0 < s < w:
        sq = [(d, s), (d, w - s)]
    elif w < s < w + d:
        s -= w
        sq = [(s, w), (d - s, w)]
    elif w + d < s < 2 * w + d:
        s -= w + d
        sq = [(d, s), (d, w - s)]
    elif 2 * w + d < s < 2 * (w + d):
        s -= 2 * w + d
        sq = [(s, w), (d - s, w)]
    else:
        assert(False)
    p1, p2 = sq
    if p1[0] * p1[1] > p2[0] * p2[1]:
        p1, p2 = p2, p1
    return [p1, p2]


while True:
    N, W, D = map(int, input().split())
    if not (N | W | D):
        break
    square = [(D, W)]
    for _ in range(N):
        p, s = map(int, input().split())
        square.extend(cut(*square.pop(p - 1), s))
    print(*sorted(d * w for d, w in square))

Fixed submission:
def cut(d, w, s):
    s %= d + w
    if 0 < s < w:
        p1, p2 = (d, s), (d, w - s)
    else:
        s -= w
        p1, p2 = (s, w), (d - s, w)
    if p1[0] * p1[1] > p2[0] * p2[1]:
        p1, p2 = p2, p1
    return [p1, p2]


while True:
    N, W, D = map(int, input().split())
    if not (N | W | D):
        break
    square = [(D, W)]
    for _ in range(N):
        p, s = map(int, input().split())
        d, w = square.pop(p - 1)
        square.extend(cut(d, w, s))
    print(*sorted(d * w for d, w in square))
Buggy python submission (verdict: Runtime Error):
def calRate(m, r):
    return int(m * (100 + r) / 100)

while True:
    x, y, s = map(int, input().split())
    if x == 0 and y == 0 and s == 0: break
    ans = 0
    for i in range(1, s):
        for j in range(1, s):
            if calRate(i, x) + calRate(j, x) == s:
                ans = max(ans, calRate(i, y) + calRate(j, y))
    print(ans)

Fixed submission:
def calRate(m, r):
    return int(1.0 * m * (100.0 + r) / 100.0)

while True:
    x, y, s = map(int, raw_input().split())
    if x == 0 and y == 0 and s == 0: break
    ans = 0
    for i in range(1, s):
        ix = calRate(i, x)
        j = int((s - ix) * 100.0 / (100.0 + x))
        if j < 1 or j > s-1:
            continue
        while True:
            if calRate(i, x) + calRate(j, x) < s:
                j += 1
            else:
                break
        if calRate(i, x) + calRate(j, x) != s:
            continue
        ans = max(ans, calRate(i, y) + calRate(j, y))
    print ans
Buggy python submission (verdict: Runtime Error):
def makeCahnge(c):
    money = c
    ret = []
    for i in [500, 100, 50, 10]:
        ret.append(money // i)
        money %= i
    return ret[::-1]

ansOut = []
while True:
    price = int(input())
    if price == 0: break
    c10, c50, c100, c500 = map(int, input().split())
    ans = 20*4+1
    anspay = [0, 0, 0, 0]
    for i10 in range(c10+1):
        for i50 in range(c50+1):
            for i100 in range(c100+1):
                for i500 in range(c500+1):
                    payment = sum(i*c for i, c in zip([i10, i50, i100, i500], [10, 50, 100, 500]))
                    
                    if payment >= price:
                        if sum(i-c+p for i, c, p in zip([i10, i50, i100, i500], [c10, c50, c100, c500], makeCahnge(payment - price))) < ans:
                            ans = sum(i-c+p for i, c, p in zip([i10, i50, i100, i500], [c10, c50, c100, c500], makeCahnge(payment - price))) 
                            anspay = [i10, i50, i100, i500]

    out = []
    for i, c in zip(anspay, [10, 50, 100, 500]):
        if i > 0:
            out.append('{} {}'.format(c, i))
    ansOut.append('\n'.join(out))
print('\n\n'.join(ansOut))

Fixed submission:
ansOut = []
coin = [10, 50, 100, 500]
while True:
    price = int(input())
    if price == 0:
        break
    cash = list(map(int, input().split()))
    sumCash = sum(c * n for c, n in zip(coin, cash))
    change = sumCash - price
    changeCoins = [(change % 50) // 10, (change % 100) // 50, (change % 500) // 100, change // 500]

    out = []
    for i in range(4):
        if cash[i] > changeCoins[i]:
            out.append('{} {}'.format(coin[i], cash[i] - changeCoins[i]))
    ansOut.append('\n'.join(out))
print('\n\n'.join(ansOut))
Buggy python submission (verdict: Runtime Error):
def dfs(r, c, n):
    if board[r][c] == n:
        return
    if board[r][c] in 'WB':
        pile.append(board[r][c])
        return 
    board[r][c] = n
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if 0 <= nr < h and 0 <= nc < w:
            dfs(nr, nc, n)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    board = [list(input()) for _ in range(h)]
    place = 0
    piles = []
    black, white = [], []
    for r in range(h):
        for c in range(w):
            if board[r][c] == '.':
                pile = []
                place += 1
                dfs(r, c, place)
                piles.append(pile)
    for i, pile in enumerate(piles):
        if not pile: continue
        for p in pile:
            if p != 'B':
                break
        else:
            black.append(i+1)
        for p in pile:
            if p != 'W':
                break
        else:
            white.append(i+1)
    ans_b, ans_w = 0, 0
    for row in board:
        for c in row:
            if c in black:
                ans_b += 1
            elif c in white:
                ans_w += 1
    print(ans_b, ans_w)

Fixed submission:
import sys
sys.setrecursionlimit(3000)
def dfs(r, c, n):
    board[r][c] = n
    drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        if 0 <= nr < h and 0 <= nc < w and board[nr][nc] != n:
            if board[nr][nc] in 'WB':
                pile.append(board[nr][nc])
                continue
            dfs(nr, nc, n)

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    board = [list(input()) for _ in range(h)]
    place = 0
    piles = []
    black, white = [], []
    for r in range(h):
        for c in range(w):
            if board[r][c] == '.':
                pile = []
                place += 1
                dfs(r, c, place)
                piles.append(pile)

    for i, pile in enumerate(piles):
        if not pile: continue
        if all(p == 'B' for p in pile):
            black.append(i+1)
        elif all(p == 'W' for p in pile):
            white.append(i+1)

    ans_b, ans_w = 0, 0
    for row in board:
        for c in row:
            if c in black:
                ans_b += 1
            elif c in white:
                ans_w += 1
    print(ans_b, ans_w)
Buggy python submission (verdict: Runtime Error):
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (1000 * 1000)
    wl = [0] * (1000 * 1000)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans

Fixed submission:
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (h[-1] + 1)
    wl = [0] * (w[-1] + 1)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans

Buggy python submission (verdict: Runtime Error):
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (1000 * 1000 + 1)
    wl = [0] * (1000 * 1000 + 1)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans

Fixed submission:
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (h[-1] + 1)
    wl = [0] * (w[-1] + 1)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans
Buggy python submission (verdict: Runtime Error):
import math
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << (math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(i) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))

Fixed submission:
import math
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << int(math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(input())
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x in X:
    dp.update(x - 1, dp.query(x - 1) + x)
print(N * (N + 1) // 2 - dp.query(N - 1))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(200000)


def dfs(v, cnt):
    group[v] = cnt
    for c in edge[v]:
        if group[c] == -1:
            dfs(c, cnt)

V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    edge[s].append(t)
    edge[t].append(s)
group = [-1] * V
c = 0
for i in range(V):
    if group[i] == -1:
        dfs(i, c)
        c += 1

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print('yes' if group[s] == group[t] else 'no')

Fixed submission:
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    edge[s].append(t)
    edge[t].append(s)

group = [-1] * V
cnt = 0
for i in range(V):
    if group[i] == -1:
        group[i] = cnt
        stack = [i]
        while stack:
            v = stack.pop()
            for c in edge[v]:
                if group[c] == -1:
                    group[c] = cnt
                    stack.append(c)
        cnt += 1
for _ in range(int(input())):
    s, t = map(int, input().split())
    print('yes' if group[s] == group[t] else 'no')

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)


def dfs(v, cnt):
    group[v] = cnt
    for c in edge[v]:
        if group[c] == -1:
            dfs(c, cnt)

V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    edge[s].append(t)
    edge[t].append(s)
group = [-1] * V
c = 0
for i in range(V):
    if group[i] == -1:
        dfs(i, c)
        c += 1

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print('yes' if group[s] == group[t] else 'no')

Fixed submission:
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t = map(int, input().split())
    edge[s].append(t)
    edge[t].append(s)

group = [-1] * V
cnt = 0
for i in range(V):
    if group[i] == -1:
        group[i] = cnt
        stack = [i]
        while stack:
            v = stack.pop()
            for c in edge[v]:
                if group[c] == -1:
                    group[c] = cnt
                    stack.append(c)
        cnt += 1
for _ in range(int(input())):
    s, t = map(int, input().split())
    print('yes' if group[s] == group[t] else 'no')
Buggy python submission (verdict: Runtime Error):
import itertools
N, Q, row, col = input(), [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q + list(zip(row, l))
    if not any((r1 != r2 or c1 != c2) and (r1 == r2 or c1 == c2 or r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen for r1, c1 in queen):
        print '\n'.join(''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8))
        break

Fixed submission:
import itertools
N, Q, row, col = input(), [], range(8), range(8)
for _ in range(N):
    r, c = map(int, raw_input().split())
    Q.append((r, c))
    row.remove(r)
    col.remove(c)
for l in itertools.permutations(col):
    queen = Q + list(zip(row, l))
    if not any((r1 != r2 or c1 != c2) and (r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2) for r2, c2 in queen for r1, c1 in queen):
        print '\n'.join(''.join('Q' if (r, c) in queen else '.' for c in range(8)) for r in range(8))
        break
Buggy python submission (verdict: Runtime Error):
import functools


@functools.lru_cache(maxsize=None)
def rec(c):
    if c <= 0:
        return 0 if c == 0 else INF
    ret = INF
    for coin in coins:
        ret = min(ret, rec(c-coin) + 1)
    return ret

INF = 10**6
N, M = map(int, input().split())
coins = [int(x) for x in input().split()]
print(rec(N))

Fixed submission:
n, m = map(int, input().split())
C = list(map(int, input().split()))
INF = 10**5
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
    for c in C:
        if i + c <= n:
            dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

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


@functools.lru_cache(maxsize=None)
def rec(c):
    if c == 0:
        return 0
    ret = INF
    for coin in coins:
        if c - coin >= 0:
            ret = min(ret, rec(c-coin) + 1)
    return ret

INF = 10**6
N, M = map(int, input().split())
sys.setrecursionlimit(N+1)
coins = [int(x) for x in input().split()]
print(rec(N))

Fixed submission:
n, m = map(int, input().split())
C = list(map(int, input().split()))
INF = 10**5
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
    for c in C:
        if i + c <= n:
            dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

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


@functools.lru_cache(maxsize=None)
def rec(c):
    if c == 0:
        return 0
    ret = INF
    for coin in coins:
        if c - coin >= 0:
            ret = min(ret, rec(c-coin) + 1)
    return ret

INF = 10**6
N, M = map(int, input().split())
coins = [int(x) for x in input().split()]
sys.setrecursionlimit(INF)
print(rec(N))

Fixed submission:
n, m = map(int, input().split())
C = list(map(int, input().split()))
INF = 10**5
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
    for c in C:
        if i + c <= n:
            dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])