Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03355 (python)

Fixed submission:
S = input()
k = int(input())
ans = set()
for i in range(len(S)):
    for j in range(1,k+1):
        ans.add(S[i:i+j])
print(sorted(ans)[k-1])

Buggy submission (verdict: Runtime Error):
import sys
from collections import deque
readline = sys.stdin.readline
n, m = map(int, readline().split())
P = list(map(lambda x:int(x)-1, readline().split()))
G = [set() for _ in range(n)]
for i in range(m):
    x, y = map(lambda x:int(x)-1, readline().split())
    G[x].add(y)
    G[y].add(x)

D = {}
cnt = 0
V = [-1]*n
while -1 in V:
    st = V.index(-1)
    que = deque([st])
    V[st] = cnt
    D[cnt] = set([P[st]])
    while que:
        nw = que.popleft()
        for nx in G[nw]:
            if V[nx] != -1: continue
            D[cnt].add(P[nx])
            V[nx] = cnt
            que.append(nx)
    cnt += 1
print(sum([int(i in D[V[i]]) for i in range(n)]))
Problem p03356 (python)

Fixed submission:
import sys
readline = sys.stdin.readline

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1]*n

    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u==v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u
        self.size[v] += self.size[u]
        self._par[u] = v

    def is_connected(self, u, v):
        return self.root(u)==self.root(v)

n, m = map(int, readline().split())
P = list(map(lambda x:int(x)-1, readline().split()))
uf = UnionFind(n)
for _ in range(m):
    x, y = map(lambda x:int(x)-1, readline().split())
    uf.unite(x,y)

ans = 0
for i in range(n):
    if uf.is_connected(i, P[i]):
        ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1]*n

    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u==v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u
        self.size[v] += self.size[u]
        self._par[u] = v

    def is_connected(self, u, v):
        return self.root(u)==self.root(v)

n, m = map(int, readline().split())
P = list(map(lambda x:int(x)-1, readline().split()))
uf = UnionFind(n)
for _ in range(m):
    x, y = map(lambda x:int(x)-1, readline().split())
    uf,unite(x,y)

ans = 0
for i in range(n):
    if uf.is_connected(i, p[i]):
        ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

class UnionFind(object):
    def __init__(self, n):
        self._par = list(range(n))
        self.size = [1]*n

    def root(self, v):
        if self._par[v] == v:
            return v
        self._par[v] = self.root(self._par[v])
        return self._par[v]
    
    def unite(self, u, v):
        u, v = self.root(u), self.root(v)
        if u==v:
            return False
        if self.size[u] > self.size[v]:
            u, v = v, u
        self.size[v] += self.size[u]
        self._par[u] = v

    def is_connected(self, u, v):
        return self.root(u)==self.root(v)

n, m = map(int, readline().split())
P = list(map(lambda x:int(x)-1, readline().split()))
uf = UnionFind(n)
for _ in range(m):
    x, y = map(lambda x:int(x)-1, readline().split())
    uf,unite(x,y)

ans = 0
for i in range(n):
    if uf.is_connected(i, p[i]):
        ans += 1
print(ans)
Problem p03361 (python)

Fixed submission:
h, w =map(int,input().split())
S=["."+input()+"." for i in range(h)]
S=["."*(w+2)]+S+["."*(w+2)]
r = 'Yes'
for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            if S[i-1][j]=="." and S[i+1][j]=="." and S[i][j-1]=="." and S[i][j+1]==".":
                r = 'No'
                break
print(r)

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
S = ['']*h
for i in range(h):
    S[i] = input()

r = 'Yes'
for i in range(1, w-1):
    for j in range(1, h-1):
        if S[i][j]=='#':
            if S[i-1][j]=='.' and S[i+1][j]=='.' or S[i][j-1]=='.' or S[i][j+1]=='.':
                r = 'No'
                break
print(r)

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
S = ['']*h
for i in range(h):
    S[i] = input()

r = 'Yes'
for i in range(1, w-1):
    for j in range(1, h-1):
        if S[i][j]=='#':
            if S[i-1][j]=='#' or S[i+1][j]=='#' or S[i][j-1]=='#' or S[i][j+1]=='#':
                continue
            else:
                r = 'No'
print(r)
Problem p03486 (python)

Fixed submission:
s = input()
t = input()
alf = 'abcdefghijklmnopqrstuvwxyz'
r = 'No'
if len(s)<len(t) and s==t[:len(s)]:
    r = 'Yes'

s = sorted(s)
t = sorted(t, reverse=True)
for i in range(min(len(s),len(t))):
    si = alf.index(s[i])
    ti = alf.index(t[i])
    if si < ti:
        r = 'Yes'
        break
    elif si == ti:
        continue
    else:
        break
print(r)

Buggy submission (verdict: Runtime Error):
s = sorted(input())
t = sorted(input(), reverse=True)
alf = 'abcdefghijklmnopqrstuvwxyz'
r = 'No'
if len(s)<len(t) and s==t[len(s):]:
    r = 'Yes'
for i in range(len(s)):
    si = alf.index(s[i])
    ti = alf.index(t[i])
    if si < ti:
        r = 'Yes'
        break
    elif si == ti:
        continue
    else:
        break
print(r)
Problem p03503 (python)

Fixed submission:
import sys
n = int(input())
F = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
P = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = -pow(10,9)-7
for i in range(1,pow(2,10)):
    b = bin(i)[2:].zfill(10)
    t = 0
    for j in range(n):
        c = 0
        for k in range(10):
            if int(b[k]) and F[j][k]:
                c += 1
        t += P[j][c]
    ans = max(ans, t)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
F = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
P = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = 0
for i in range(1,pow(2,10)):
    b = bin(i)[2:].zfill(10)
    t = 0
    for j in range(n):
        c = 0
        for k in range(10):
            if int(b[k]) and F[j][k]:
                c += 1
        a += P[j][c]
    ans = max(ans, a)
print(ans)
Problem p03578 (python)

Fixed submission:
n = int(input())
dD = input().split()
m = int(input())
dT = input().split()
d = dict()

for di in dD:
    if di in d:
        d[di] += 1
    else:
        d[di] = 1

ans = 'YES'
for ti in dT:
    if ti not in d or d[ti]==0:
        ans = 'NO'
        break
    else:
        d[ti] -= 1
print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
D = list(map(int, input().split()))
m = int(input())
T = list(map(int, input().split()))
D.sort()
T.sort()
if n=<m:
    if D==T:
        print('YES')
        exit()
    else:
        print('NO')
        exit()

r = 'YES'
for i in range(m):
    if T[i] in D:
        idx = D.index(T[i])
        D = D[idx+1:]
    else:
        r = 'NO'
        break
print(r)
Problem p03583 (python)

Fixed submission:
N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        if 4*h*n-N*n-N*h>0 and (N*h*n)%(4*h*n-N*n-N*h)==0:
            print(h, n, (N*h*n)//(4*h*n-N*n-N*h))
            exit()

Buggy submission (verdict: Runtime Error):
n = int(input())
if n%2==0:
    print(n, n, n//2)
else:
    f = False
    for i in range(1, 3500):
        _h = n/i
        for j in range(1,3500):
            _n = n/j
            w = n/(4-_h-_n)
            if w>0 and w%1==0:
                print(i, j, int(w))
                f = True
            if f: break
        if f: break

Buggy submission (verdict: Runtime Error):
n = int(input())
if n%2==0:
    print(n, n, n//2)
else:
    f = False
    for i in range(1, 3500):
        _h = n/i
        for j in range(1,3500):
            _n = n/j
            w = n/(4-_h-_n)
            if w>0 and w%1==0:
                print(i, j, int(w))
                f = True
            if f: break
        if f: break
Problem p03593 (python)

Fixed submission:
from collections import Counter
h, w = map(int, input().split())
A = []
for i in range(h):
    A.extend(list(input()))
cA = Counter(A)

l1 = h*w%2
l2 = (h//2)*(w%2) + (w//2)*(h%2)
l3 = (h//2)*(w//2)
if l1:
    for key, val in cA.items():
        if val%2==1:
            cA[key] -= 1
            break
for _ in range(l2):
    for key, val in cA.items():
        if val%4==2:
            cA[key] -= 2
            break
print('Yes' if sum(val%4 for val in cA.values()) == 0 else 'No')

Buggy submission (verdict: Runtime Error):
from collections import Counter
h, w = map(int, input().split())
A = []
for i in range(h):
    A.extend(list(input()))
cA = Counter(A)

l1 = h*w%2
l2 = (h//2)*(w%2) + (w//2)*(h%2)
l3 = (h//2)*(w//2)
if l1:
    for key, val in cA.items():
        if val%2==1:
            cA[key] -= 1
            break
for _ in range(l2):
    for key, val in cA.items():
        if val%4=-2:
            cA[key] -= 2
            break
print('Yes' if sum(val%4 for val in cA.values()) == 0 else 'No')

Buggy submission (verdict: Runtime Error):
from collections import Counter
h, w = map(int, input().split())
A = []
for i in range(h):
    A.extend(list(input()))
cA = Counter(A)

l1 = h*w%2
l2 = (h//2)*(w%2) + (w//2)*(h%2)
l3 = (h//2)*(w//2)
if l1:
    for key, val in cA.items():
        if val%2==1:
            cA[key] -= 1
            break
for _ in range(l2):
    for key, val in cA.items():
        if val%4=-2:
            cA[key] -= 2
            break
print('Yes' if sum(a[i]%4 for i in a) == 0 else 'No')
Problem p03612 (python)

Fixed submission:
n = int(input())
P = list(map(int, input().split()))

r = 0
for i in range(n):
    if P[i] == i+1:
        if i!=n-1:
            P[i+1] = P[i]
            r += 1
        else:
            r += 1
print(r)

Buggy submission (verdict: Runtime Error):
n = int(input())
P = list(map(int, input().split()))

r = 0
for i in range(n):
    if P[i] == i+1:
        if i!=n:
            P[i+1] = P[i]
            r += 1
        else:
            r += 1
print(r)
Problem p03645 (python)

Fixed submission:
def main():
    n, m = map(int, input().split())
    Ton, Fr1 = set(), set()
    for _ in range(m):
        a, b = map(int, input().split())
        if b==n:
            Ton.add(a)
        if a==1:
            Fr1.add(b)

    print('POSSIBLE' if Ton&Fr1 else 'IMPOSSIBLE')

main()

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
Ton = [False]*n
Fr1 = [False]*n
for i in range(m):
    a, b = map(int, input().split())
    if b==n:
        Ton[a] = True
    if a==1:
        Fr1[b] = True

r = 'IMPOSSIBLE'
for i in range(m):
    if Ton[i]==Fr1[i]==True:
        r = 'POSSIBLE'
print(r)
Problem p03695 (python)

Fixed submission:
#cant fix re, just copy and paste.
n = int(input())
a = list(map(int, input().split()))
a.sort()
free=0
cset=set()
for rate in a:
    color = int(rate / 400)
    if color >=8:
        free+=1
    else:
        cset.add(color)

colormin=len(cset)
colormax=colormin+free
 
print(str(max(1,colormin)), colormax)

Buggy submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
k = [0]*n
mk = [0]*8
for i in range(n):
    k[i] = A[i]//400
    mk[k[i]-1] += 1
r1 = len(set(k))-min(1, mk[-1])
r2 = r1+mk[-1]
print(str(r1)+" "+str(r2))

Buggy submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
k = [0]*n
mk = [0]*8
for i in range(n):
    k[i] = A[i]//400
    mk[k[i]-1] += 1
if mk[-1]:
    print(len(set(k))-1, min(len(set(k))-1+mk[-1], 8))
else:
    print(len(set(k)), len(set(k)))
Problem p03854 (python)

Fixed submission:
s = input().replace('eraser', '').replace('erase', '').replace('dreamer', '').replace('dream', '')
print('YES' if s=='' else 'NO')

Buggy submission (verdict: Runtime Error):
s = input()replace('dreamer', '').replace('eraser', '').replace('dream', '').replace('erase', '').
print('YES' if s=='' else 'NO')
Problem p04020 (python)

Fixed submission:
import sys
n = int(sys.stdin.readline())
ans = 0
t = 0
for i in range(n):
    a = int(sys.stdin.readline())
    if a==0:
        ans += t//2
        t = 0
    else:
        t += a
if t>0: ans += t//2
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
n = int(sys.stdin.readline())
ans = 0
t = 0
for i in range(n):
    a = int(sys.stdin.readline())
    if a==0:
        ans += t//2
        t = 0
    else:
        t += a
if t>0: ans += t//2
pritn(ans)
Problem p02696 (python)

Fixed submission:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    A, B, N = map(int, input().split())

    def func(x):
        res = (A * x) // B - A * (x // B)
        return res

    print(func(min(N, B - 1)))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    A, B, N = map(int, input().split())

    def func(x):
        res = (A * x) // B - A * (x // B)
        return res

    M = 0
    for i in range(N, max(0, N - 10 ** 8), -1):
        tmp = func(i)
        print(i, tmp)
        if tmp > M:
            M = tmp

    print(M)


if __name__ == "__main__":
    main()
Problem p02697 (python)

Fixed submission:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    if N % 2 == 0:
        for i in range(M):
            x = i + 1
            y = N - i - 1
            if y - x > (N - y + x):
                print(x, y)
            else:
                print(x, y - 1)
    else:
        for i in range(M):
            print(i + 1, N - i)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    if N % 2 == 0:
        used = [False] * (N + 1)
        i = 0
        span = 1
        cnt = 0
        while cnt < M:
            cnt += 1
            while used[i]:
                i += 1
            print(i + 1, i + 1 + span)
            used[i] = True
            used[i + span] = True
            span += 1
    else:
        for i in range(M):
            print(i + 1, N - i)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    if N % 2 == 0:
        used = [False] * (N + 1)
        i = 1
        span = 1
        cnt = 0
        while cnt < M:
            cnt += 1
            while used[i]:
                i += 1
            print(i, i + span)
            used[i] = True
            used[i + span] = True
            i += 1
            span += 1
    else:
        for i in range(M):
            print(i + 1, N - i)


if __name__ == "__main__":
    main()
Problem p02742 (python)

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

if H == 1 or W == 1:
    print(1)
else:
    if (H * W) % 2 == 1:
        ans = H * W // 2 + 1
    else:
        ans = H * W // 2
    print(ans)

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

if H == 1 or W == 1:
    print(1)
else:
    if (H * W) % 2 == 1:
        ans = H * W // 2 + 1
    else:
        ans = H * W // 2
print(ans)
Problem p02803 (python)

Fixed submission:
from collections import deque

H, W = map(int, input().split())

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input() + "#"
grid += "#" * W


def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)

Buggy submission (verdict: Runtime Error):
from collections import deque

H, W = map(int, input().split())

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input().split()
grid += "#" * W


def bfs(start):
    INF = 10 * 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)
Problem p02812 (python)

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

ans = 0
for i in range(N):
    if S[i : i + 3] == "ABC":
        ans += 1

print(ans)

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

ans = 0
i = 0
while i < N:
    if S[i] == "A":
        i += 1
        if S[i] == "B":
            i += 1
            if S[i] == "C":
                ans += 1
            else:
                i += 1
        else:
            i += 1
    else:
        i += 1

print(ans)
Problem p02837 (python)

Fixed submission:
def is_nth_bit_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


N = int(input())
comment = {}
for i in range(N):
    A = int(input())
    comment[i] = []
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        comment[i].append((x, y))

ans = 0
for i in range(2 ** N):
    judge = [None] * N
    flag = True
    for j in range(N):
        honest = is_nth_bit_set(i, j)
        judge[j] = honest

    for j in range(N):
        honest = judge[j]
        if not honest:
            continue
        for x, y in comment[j]:
            if honest:
                if judge[x] == y:
                    continue
                else:
                    flag = False
                    break
    if not flag:
        continue

    tmp = sum(judge)
    if tmp > ans:
        ans = tmp
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = []

for _ in range(N):
    a = int(input())
    xy = []
    for _ in range(a):
        x, y = map(int, input().split())
        xy.append((x, y))
    A.append(xy)

ans = 0
cnt = 0
bit = format(cnt, "#015b")
for _ in range(2 ** N):
    d = {}
    for i in range(N):
        d[i] = int(bit[-i])

    flag = False
    for i in range(N):
        for x, y in A[i]:
            if d[i] == 1:
                if d[x - 1] == y:
                    pass
                else:
                    flag = True
                    break
            else:
                if d[x - 1] == y:
                    flag = True
                    break
                else:
                    pass

        if flag:
            break

    if flag:
        cnt += 1
        bit = format(cnt, "#015b")
        continue

    a = sum(list(map(int, list(bit[2:]))))
    ans = max(a, ans)
    cnt += 1
    bit = format(cnt, "#015b")


print(ans)
Problem p02845 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        if a not in cnt:
            print(0)
            return
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()
Problem p02936 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, Q = map(int, input().split())

    edges = [[] for _ in range(N + 1)]
    nums = [0 for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

    for _ in range(Q):
        p, x = map(int, input().split())
        nums[p] += x

    def dfs(now, parent):
        for i in edges[now]:
            if i != parent:
                nums[i] += nums[now]
                dfs(i, now)

    dfs(1, 0)
    for n in nums[1:]:
        print(n)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)
N, Q = map(int, input().split())
A, B = [], []

edges = [[] for _ in range(N + 1)]
nums = [0 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    nums[p] += x


def dfs(now, parent):
    for i in edges[now]:
        if i != parent:
            nums[i] += nums[now]
            dfs(i, now)


dfs(1, 0)
for n in nums[1:]:
    print(n)

Buggy submission (verdict: Runtime Error):
N, Q = map(int, input().split())
A, B = [], []

edges = [[] for _ in range(N + 1)]
nums = [0 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    nums[p] += x


def dfs(now, parent):
    for i in edges[now]:
        if i != parent:
            nums[i] += nums[now]
            dfs(i, now)


dfs(1, 0)
for n in nums[1:]:
    print(n)