Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for c in C:
    for b in B:
        if b >= c: break
            
        for a in A:
            if a >= b: break
            ans += 1
print(ans)

Fixed submission:
import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    i_a = bisect.bisect_left(A, b)
    i_c = bisect.bisect_right(C, b)
    ans += i_a * (N-i_c)
print(ans)
Buggy python submission (verdict: Runtime Error):
class UnionFindWithRank:
    # par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
    def __init__(self, size:int):
        self.par = [-1]*size
        self.rank = [0]*size
        for i in range(size):
            self.par[i] = i
    
    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
        
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        
        # 短いほうを長いほうにくっつける
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
        else:
            self.par[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
                

##### main #####
N,M = map(int, input().split())
a,b = [0]*M, [0]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i==j: continue # この辺はパス
        uf.unite(a[j], b[j])
    bridge = False
    for i in range(N):
        if not uf.isSame(0,i):
            bridge = True
    if bridge:
        ans += 1
print(ans)

Fixed submission:
# C
N,M = map(int, input().split())
graph = [[False]*N for _ in range(N)]
visited = [False]*N

def dfs(cur):
    global visited
    visited[cur] = True
    for nxt in range(N):
        if graph[cur][nxt]==False: continue
        if visited[nxt]==True: continue
        dfs(nxt)


a = [-1]*M
b = [-1]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

ans = 0
for i in range(M):
    graph[a[i]][b[i]] = False # 辺を消す
    graph[b[i]][a[i]] = False
    # print("graph: "+"\n".join(map(str, graph)))
    visited = [False]*N
    dfs(0)
    if not all(visited):
        ans += 1
    graph[a[i]][b[i]] = True # 辺を戻す
    graph[b[i]][a[i]] = True
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*h*n -N*h -N*n <= 0: continue
        w = N*h*n/(4*h*n -N*h -N*n)
        if not 0<w<=3500: continue 
        if w.is_integer()==True:
            print(h,n,int(w))
            sys.exit()

Fixed submission:
import sys
N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if 4*h*n -N*h -N*n <= 0: continue
        w = N*h*n/(4*h*n -N*h -N*n)
        if not 0<w<=3500: continue 
        if w.is_integer()==True:
            print(h,n,int(w))
            sys.exit()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
N = int(input())

for h in range(1, 3501):
    for n in range(1, h+1):
        if (4/N - 1/h - 1/n) == 0: continue
        w = 1 // (4/N - 1/h - 1/n)
        if 0 < w and 4/N == 1/h + 1/n + 1/w:
            print(h, n, int(w))
            sys.exit()


Fixed submission:
import sys

N = int(input())
for h in range(1, 3501):
    for n in range(1, h+1):
        if (4*h*n - N*h - N*n) <= 0:
            continue
        w_int = N*h*n // (4*n*h - N*h - N*n)
        w_float = N*h*n / (4*n*h - N*h - N*n)
        if w_int == w_float:
            print(h, n, w_int)
            sys.exit()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (4/N - 1/h - 1/n) == 0: continue
        w = 1 // (4/N - 1/h - 1/n)
        if 0 < w <= 3500 and 4/N == 1/h + 1/n + 1/w:
            print(h, n, int(w))
            sys.exit()


Fixed submission:
import sys

N = int(input())
for h in range(1, 3501):
    for n in range(1, h+1):
        if (4*h*n - N*h - N*n) <= 0:
            continue
        w_int = N*h*n // (4*n*h - N*h - N*n)
        w_float = N*h*n / (4*n*h - N*h - N*n)
        if w_int == w_float:
            print(h, n, w_int)
            sys.exit()
Buggy python submission (verdict: Runtime Error):
# C sugar water
from collections import deque
def noudo(water, sugar):
    if water+sugar==0: return 0
    return 100*sugar/(water+sugar)

A,B,C,D,E,F = map(int, input().split())
q = deque([(0,0)]) # water, sugar
max_noudo = 0
ans = None
while q:
    water,sugar = q.popleft()
    cur = noudo(water, sugar)
    if cur>max_noudo:
        ans = (water, sugar)
        max_noudo = cur
    for dw,ds in [(100*A, 0), (100*B, 0), (0,C), (0,D)]:
        if noudo(water+dw, sugar+ds)>noudo(100, E) or water+dw+sugar+ds>F: continue
        q.append((water+dw, sugar+ds))
        
water, sugar = ans
print(water+sugar, sugar)

Fixed submission:
from fractions import gcd
A,B,C,D,E,F = map(int, input().split())
ans = {"w":A*100, "s":0}
def density(water, sugar):
    return 100*sugar/(water+sugar)

G = gcd(C,D)
for a in range(31):
    for b in range(31):
        water = (a*A+b*B)*100
        if water>F:
            continue
        max_sugar = min((a*A+b*B)*E, F-water)
        sugar = int(G*(max_sugar//G))
        if sugar<min(C,D): continue
        if water+sugar==0: 
            continue
        if density(water, sugar)>density(ans["w"], ans["s"]):
            ans["w"] = water
            ans["s"] = sugar
            #print(water, sugar)
print(ans["w"]+ans["s"], ans["s"])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

l = []
for _ in range(N):
    a = int(input())
    if a in l:
        l.remove(a)
    else:
        l.append(a)
print(len(l))

Fixed submission:
N = int(input())

l = set([])
for _ in range(N):
    a = int(input())
    if a in l:
        l.remove(a)
    else:
        l.add(a)
print(len(l))
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = list(map(int, input().split()))

cnt = [0]*(int(1e9)+1)
for ai in a:
    cnt[ai] += 1

ans = 0
condi = 0
for ai in a[::-1]:
    if cnt[ai] >= 4:
        ans = max(ans, ai*ai)
        break
    else:
        if condi==0:
            condi = ai
        else:
            ans = condi * ai
            break
            
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)[::-1]
cur = A[0]
cnt = 0
ans = []
for ai in A:
    if ai==cur: cnt += 1
    else: 
        cur = ai
        cnt = 1
    if cnt==2 or cnt==4:
        ans.append(cur)
    if len(ans)==2:
        print(ans[0]*ans[1])
        break
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
from math import gcd
N = int(input())

ans = int(input())
for _ in range(N-1):
    t = int(input())
    g = gcd(t, ans)
    ans = ans*t//g
print(ans)

Fixed submission:
N = int(input())

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

lcm = 1
for i in range(N):
    t = int(input())
    lcm = t*lcm // gcd(lcm, t)

print(lcm)

Buggy python submission (verdict: Runtime Error):
N = int(input())
T = list((int(input()) for i in range(N)))
    
    
def gcd2(a, b):
    if b == 0: return a
    return gcd2(b, a%b)

def lcm2(a, b):
    return int(a*b/gcd2(a, b))

def lcm(l):
    while len(l) > 1:
        tmp = lcm2(l.pop(), l.pop())
        l.append(tmp)
        
    return l[0]

print(lcm(T))

Fixed submission:
N = int(input())

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a%b)

lcm = 1
for i in range(N):
    t = int(input())
    lcm = t*lcm // gcd(lcm, t)

print(lcm)
Buggy python submission (verdict: Runtime Error):
# D
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf')]*N # from K
visited = [False]*N
q = [K]
dist[K] = 0
visited[K] = True
while q:
    cur = q.pop()
    visited[cur] = True
    for nex,cost in edge[cur]:
        if not visited[nex]:
            q.append(nex)
            dist[nex] = dist[cur]+cost
#print(dist)
for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])

Fixed submission:
# D
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    ai,bi,ci = map(int, input().split())
    edge[ai-1].append((bi-1, ci))
    edge[bi-1].append((ai-1, ci))
Q,K = map(int, input().split())
K = K-1
x,y = [],[]
for _ in range(Q):
    xi,yi = map(int, input().split())
    x.append(xi-1)
    y.append(yi-1)


dist = [float('inf')]*N # from K
visited = [False]*N
q = [K]
dist[K] = 0
visited[K] = True
while q:
    cur = q.pop()
    visited[cur] = True
    for nex,cost in edge[cur]:
        if not visited[nex]:
            q.append(nex)
            dist[nex] = dist[cur]+cost
#print(dist)
for xi,yi in zip(x,y):
    print(dist[xi] + dist[yi])
Buggy python submission (verdict: Runtime Error):
# D
N,A,B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)

max_mean = sum(v[:A])/A
print(max_mean)

from collections import Counter
from math import factorial

def comb(n,r):
    return factorial(n)//(factorial(r)*factorial(n-r))

v_count = Counter(v)
ans = 0
if v[0]==v[A-1]:
    n = v_count[v[A-1]]
    for r in range(A, B+1):
        if r>n: break
        ans += comb(n, r)
else:
    print(n, r)
    n = v_count[v[A-1]]
    select_count = Counter(v[:A])
    r = select_count[v[A-1]]
    ans = comb(n,r)
print(ans)

Fixed submission:
# D
N,A,B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)

max_mean = sum(v[:A])/A
print(max_mean)

from collections import Counter
from math import factorial

def comb(n,r):
    return factorial(n)//(factorial(r)*factorial(n-r))

v_count = Counter(v)
ans = 0
if v[0]==v[A-1]:
    n = v_count[v[A-1]]
    for r in range(A, B+1):
        if r>n: break
        ans += comb(n, r)
else:
    #print(n, r)
    n = v_count[v[A-1]]
    select_count = Counter(v[:A])
    r = select_count[v[A-1]]
    ans = comb(n,r)
print(ans)

Buggy python submission (verdict: Runtime Error):
# D
N,A,B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)

max_mean = sum(v[:A])/A
print(max_mean)

from collections import Counter
from math import factorial

def comb(n,r):
    return factorial(n)//(factorial(r)*factorial(n-r))

v_count = Counter(v)
ans = 0
if v[0]==v[A-1]:
    n = v_count[v[A-1]]
    for r in range(A, B+1):
        ans += comb(n, r)
else:
    n = v_count[v[A-1]]
    select_count = Counter(v[:A])
    r = select_count[v[A-1]]
    ans = comb(n,r)
print(ans)

Fixed submission:
# D
N,A,B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)

max_mean = sum(v[:A])/A
print(max_mean)

from collections import Counter
from math import factorial

def comb(n,r):
    return factorial(n)//(factorial(r)*factorial(n-r))

v_count = Counter(v)
ans = 0
if v[0]==v[A-1]:
    n = v_count[v[A-1]]
    for r in range(A, B+1):
        if r>n: break
        ans += comb(n, r)
else:
    #print(n, r)
    n = v_count[v[A-1]]
    select_count = Counter(v[:A])
    r = select_count[v[A-1]]
    ans = comb(n,r)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import  deque

x = int(input())

q = deque()
q.append((0, 0)) # (t, pos)
while q:
    t, pos = q.popleft()
#     print(t, pos)
    if pos == x:
        print(t)
        break
    else:
        q.append((t+1, pos))
        q.append((t+1, pos+t+1))
        if pos-t >= 1:
            q.append((t+1, pos-t-1))

Fixed submission:
x = int(input())
s = 0
for i in range(1, x+1):
    s += i
    if s >= x:
        print(i)
        break
Buggy python submission (verdict: Runtime Error):
import sys
S = input()
S = S[::-1]
while S:
    if S[:3]=="res":
        if S[:6]=="resare":
            S = S[6:]
            print(S)
        else:
            print("NO")
            sys.exit()

    elif S[:3]=="esa":
        if S[:5]=="esare":
            S = S[5:]
            print(S)
        else:
            print("NO")
            sys.exit()
    
    elif S[:3]=="rem":
        if S[:7]=="remaerd":
            S = S[7:]
            print(S)
        else:
            print("NO")
            sys.exit()
        
    elif S[:3]=="mae":
        if S[:5]=="maerd":
            S = S[5:]
            print(S)
        else:
            print("NO")
            sys.exit()
            
    else:
        print("NO")
        sys.exit()
else:
    print("YES")

Fixed submission:
import sys
S = input()
S = S[::-1]
while S:
    if S[:3]=="res":
        if S[:6]=="resare":
            S = S[6:]
#             print(S)
        else:
            print("NO")
            sys.exit()

    elif S[:3]=="esa":
        if S[:5]=="esare":
            S = S[5:]
#             print(S)
        else:
            print("NO")
            sys.exit()
    
    elif S[:3]=="rem":
        if S[:7]=="remaerd":
            S = S[7:]
#             print(S)
        else:
            print("NO")
            sys.exit()
        
    elif S[:3]=="mae":
        if S[:5]=="maerd":
            S = S[5:]
#             print(S)
        else:
            print("NO")
            sys.exit()
            
    else:
        print("NO")
        sys.exit()
else:
    print("YES")
Buggy python submission (verdict: Runtime Error):
W,H,N = 5,4,3
s = set([])
for h in range(H):
    for w in range(W):
        s.add((w+0.5, h+0.5))
# print(s)

for _  in range(N):
    x,y,a = map(int, input().split())
    rm = set([])
    if a==1:
        for si in s:
            if si[0]<x: rm.add(si)
    if a==2:
        for si in s:
            if si[0]>x: rm.add(si)
    if a==3:
        for si in s:
            if si[1]<y: rm.add(si)
    if a==4:
        for si in s:
            if si[1]>y: rm.add(si)
    s = s - rm
                
print(len(s))

Fixed submission:
W,H,N = map(int, input().split())
s = set([])
for h in range(H):
    for w in range(W):
        s.add((w+0.5, h+0.5))
# print(s)

for _  in range(N):
    x,y,a = map(int, input().split())
    rm = set([])
    if a==1:
        for si in s:
            if si[0]<x: rm.add(si)
    if a==2:
        for si in s:
            if si[0]>x: rm.add(si)
    if a==3:
        for si in s:
            if si[1]<y: rm.add(si)
    if a==4:
        for si in s:
            if si[1]>y: rm.add(si)
    s = s - rm
                
print(len(s))
Buggy python submission (verdict: Runtime Error):
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max(-(-t//nt), -(-a//na)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)


Fixed submission:
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max((t-1)//nt+1, (a-1)//na+1)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)

Buggy python submission (verdict: Runtime Error):
from math import ceil
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    r = 1
    if nt<t:
        r *= ceil(t/nt)
    if na*r<a:
        r *= ceil(a/na)
    na = r*na
    nt = r*nt
    t,a = nt,na
    #print(t, a)
print(t+a)

Fixed submission:
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max((t-1)//nt+1, (a-1)//na+1)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)

Buggy python submission (verdict: Runtime Error):
from math import ceil
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    r = 1
    if nt<t:
        r *= ceil(t/nt)
    if na<a:
        r *= ceil(a/na)
    na = r*na
    nt = r*nt
    t,a = nt,na
    #print(t, a)
print(t+a)

Fixed submission:
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max((t-1)//nt+1, (a-1)//na+1)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)
Buggy python submission (verdict: Time Limit Exceeded):
X = input()
N = len(X)//2
for _ in range(N):
    X = X.replace("ST", "")
print(len(X))

Fixed submission:
X = input()
s = []
for x in X:
    if x=="T":
        if s==[] or s[-1]=="T":
            s.append(x)
        else:
            s.pop()
    else: # x=="S"
        s.append(x)
    #print(x, s)
print(len(s))
Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial

def P(n, r):
    return factorial(n)//factorial(n-r)

def C(n, r):
    return P(n, r)//factorial(r)


ans = 0
H,W,A,B = map(int, input().split())
MOD = int(1e9)+7

for i in range(min(H-A, W-B)):
    ans += C(H-A+B-1, B+i)*C(A+W-B-1, A+i)
#     print(ans)
    ans %= MOD
    
print(ans)

Fixed submission:
MOD = 10**9 + 7
MAX = 2*10**5
fac = [0]*MAX  # fac[n]:  (n!) mod p
finv = [0]*MAX  # finv[n]: (n!)^-1 mod p
inv = [0]*MAX  # inv[n]:  (n)^-1 mod -p


def comb_init():
    global fac, finv, inv
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD


def comb(n: int, r: int) -> int:
    global fac, finv
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD


H, W, A, B = map(int, input().split())
comb_init()
ans = 0

for i in range(H-A):
    x = comb(B-1+i, i)
    a = H-1-i
    b = W-1-B
    x *= comb(a+b, a)
    x %= MOD
    ans += x
ans %= MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
k = int(input())        
    if (k%2) == 0:
        o = (k*(k+1))/2
        e = (k*(k-1))/2
        print(o+e)
    else:
        o = (k*(k-1))/2
        e = (k*(k-1))/2
        print(o+e)

Fixed submission:
#おそらく上は偶数の処理がおかしい
k = int(input())        
#奇数の場合
if (k%2) == 1:
    o = (k-1) * (k+1) / 8
    #eはoと同じ数値
    print(int(2*o))
#偶数の場合 
else:
    o = k * (k+2) / 8
    e = k * (k-2) / 8
    print(int(o+e))

Buggy python submission (verdict: Runtime Error):
k = int(input())
print((k+1) * (K // 2) / 2)

Fixed submission:
#おそらく上は偶数の処理がおかしい
k = int(input())        
#奇数の場合
if (k%2) == 1:
    o = (k-1) * (k+1) / 8
    #eはoと同じ数値
    print(int(2*o))
#偶数の場合 
else:
    o = k * (k+2) / 8
    e = k * (k-2) / 8
    print(int(o+e))
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcdArr(a):
    return reduce(gcd, a)

n = int(input())
ret = 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        for c in range(1, n + 1):
            ret += gcdArr((a, b, c))
print(ret)

Fixed submission:
from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcdArr(a):
    return reduce(gcd, a)

n = int(input())
ret = 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        gcd_ = gcd(a, b)
        if gcd_ == 1:
            ret += n
            continue
        for c in range(1, n + 1):
            ret += gcd(gcd_, c)
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

d = defaultdict(int)
for _ in range(int(input())):
    d[input()] += 1
print('\n'.join(sorted([k for k in d.keys() if d[k] == max(d.values())])))

Fixed submission:
from collections import defaultdict

d = defaultdict(int)
for _ in range(int(input())):
    d[input()] += 1
mx = max(d.values())
print('\n'.join(sorted([k for k in d.keys() if d[k] == mx])))
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
attack = [None] * n
cost = [None] * n
for i in range(n):
    a, c = map(int, input().split())
    attack[i] = a
    cost[i] = c
dp = [0] + [float('inf')] * h
for i in range(1, h + 1):
    for j in range(n):
        dp[i] = min(dp[i], cost[j] + dp[max(0, i - attack[j])])
print(dp[h])

Fixed submission:
from sys import stdin

h, n = map(int, stdin.readline().split())
attack = [None] * n
cost = [None] * n
for i in range(n):
    a, c = map(int, stdin.readline().split())
    attack[i] = a
    cost[i] = c
dp = [0] + [float('inf')] * h
for i in range(1, h + 1):
    for j in range(n):
        dp[i] = min(dp[i], cost[j] + dp[max(0, i - attack[j])])
print(dp[h])
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

money = [0,1,2,3,4,5]
n = int(input())
p = 0
lm = n//100
need = n - (lm*100)
@lru_cache(None)
def dfs( cur,limit):
    global p,need
    if not p:
        for i in range(6):
            now = cur+money[i]
            if limit+1 == lm:
                if now == need:
                    p =1
                    break
            elif limit+1<=lm:
                dfs(now,limit+1)
if n>=100:
    dfs(0,0)
    print(1 if p else 0)
else:
    print(0)


Fixed submission:
has = int(input())
dp = [False] * (has + 1)
dp[0] = True
for i in range(100, has + 1):
    for p in range(100, 106):
        if i - p >= 0:
            dp[i] |= dp[i - p]
print(1 if dp[has] else 0)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000)

MOD = 1000000007

def dfs(par, v):
    val = nColors - 1 if par == 0 else nColors - 2
    for child in edges[v]:
        if child != par:
            ways[child] = max(0, val)
            val -= 1
            dfs(v, child)

nVertices, nColors = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

ways = [0] * (nVertices + 1)
ways[1] = nColors
dfs(0, 1)
ret = 1
for w in ways[1:]:
    ret = (ret * w) % MOD
print(ret)

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

MOD = 1000000007

def dfs(par, v, val):
    for child in edges[v]:
        if child != par:
            ways[child] = max(0, val)
            val -= 1
            dfs(v, child, nColors - 2)

nVertices, nColors = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

ways = [0] * (nVertices + 1)
ways[1] = nColors
dfs(0, 1, nColors - 1)
ret = 1
for w in ways[1:]:
    ret = (ret * w) % MOD
print(ret)

Buggy python submission (verdict: Runtime Error):
MOD = 1000000007

def dfs(par, v, val):
    for child in edges[v]:
        if child != par:
            ways[child] = max(0, val)
            val -= 1
            dfs(v, child, nColors - 2)

nVertices, nColors = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

ways = [0] * (nVertices + 1)
ways[1] = nColors
dfs(0, 1, nColors - 1)
ret = 1
for w in ways[1:]:
    ret = (ret * w) % MOD
print(ret)

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

MOD = 1000000007

def dfs(par, v, val):
    for child in edges[v]:
        if child != par:
            ways[child] = max(0, val)
            val -= 1
            dfs(v, child, nColors - 2)

nVertices, nColors = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nVertices - 1):
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

ways = [0] * (nVertices + 1)
ways[1] = nColors
dfs(0, 1, nColors - 1)
ret = 1
for w in ways[1:]:
    ret = (ret * w) % MOD
print(ret)