Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):


def merge(p1, p2):
    inds = list(set(p1 + p2))
    inds.sort(key=lambda i: a[i],reverse=True)
    return inds[:2]


n = input()
a = map(int, raw_input().split())
a.append(0) #default value used for a[-1]

best = a[0]
dp = [[i, -1] for i in range(1 << n)]
for mask in range(1, len(dp)):
    for j in range(n):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])
    best = max(best, sum(map(lambda x: a[x], dp[mask])))
    print(best)


Fixed submission:


def merge(a, b):
    if a[0] > b[0]:
        if a[1] > b[0]:
            return a
        return a[0], b[0]
    if b[1] > a[0]:
        return b
    return b[0], a[0]


n = input()
a = map(int, raw_input().split())

dp = [(a[i], 0) for i in range(1 << n)]
for j in range(n):
    for mask in range(1, len(dp)):
        if mask & (1 << j):
            dp[mask] = merge(dp[mask], dp[mask ^ (1 << j)])

best = a[0]
for i in range(1, len(dp)):
    best = max(best, sum(dp[i]))
    print(best)
Buggy python submission (verdict: Time Limit Exceeded):
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n, k = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
ans = [0 for _ in range(n)]

for i in range(1, n):
	t = int(1e9)

	for j in range(1, k+1):
		if i-j >= 0: t = min(t, ans[i-j] + abs(q[i-j] - q[i]))

	ans[i] = t

print(ans[n-1])


Fixed submission:
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
import numpy as np
n, k = [int(x) for x in input().split()]
q = np.array([int(x) for x in input().split()])
ans = np.zeros(n, dtype=int)

for i in range(1, n):
	start = max(0, i-k)
	ans[i] = min(ans[start:i] + np.abs(q[i] - q[start:i]))

print(ans[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n, k = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
ans = [0]

for i in range(1, n):
	t = int(1e9)
	for j in range(1, k+1):
		if i-j >= 0: t = min(t, ans[i-j] + abs(q[i-j] - q[i]))

	ans.append(t)

print(ans[n-1])


Fixed submission:
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
import numpy as np
n, k = [int(x) for x in input().split()]
q = np.array([int(x) for x in input().split()])
ans = np.zeros(n, dtype=int)

for i in range(1, n):
	start = max(0, i-k)
	ans[i] = min(ans[start:i] + np.abs(q[i] - q[start:i]))

print(ans[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n, k = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
ans = [None for _ in range(n)]
ans[0] = 0

for i in range(1, n):
	t = int(1e9)
	for j in range(1, k+1):
		if i-j >= 0: t = min(t, ans[i-j] + abs(q[i-j] - q[i]))

	ans[i] = t

print(ans[n-1])


Fixed submission:
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
import numpy as np
n, k = [int(x) for x in input().split()]
q = np.array([int(x) for x in input().split()])
ans = np.zeros(n, dtype=int)

for i in range(1, n):
	start = max(0, i-k)
	ans[i] = min(ans[start:i] + np.abs(q[i] - q[start:i]))

print(ans[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
x, y = [int(x) for x in input().split()]
if x == y or y == 1:
	print(-1)
else:
	temp = x
	while(temp%y == 0):
		temp += x
	print(temp)

Fixed submission:
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
x, y = [int(x) for x in input().split()]
if x == y or y == 1 or x%y == 0:
	print(-1)
else:
	temp = x
	while(temp%y == 0):
		temp += x
	print(temp)

Buggy python submission (verdict: Time Limit Exceeded):
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
x, y = [int(x) for x in input().split()]
if x == y:
	print(-1)
else:
	temp = x
	while(temp%y == 0):
		temp += x
	print(temp)

Fixed submission:
# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
x, y = [int(x) for x in input().split()]
if x == y or y == 1 or x%y == 0:
	print(-1)
else:
	temp = x
	while(temp%y == 0):
		temp += x
	print(temp)
Buggy python submission (verdict: Time Limit Exceeded):
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

N,M = map(int,input().split())
S = input()
T = input()

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(p):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
			break
print(re)

Fixed submission:
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

N,M = map(int,input().split())
S = input()
T = input()

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(0,p,max((p//N),(p//M))):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
			break
print(re)

Buggy python submission (verdict: Time Limit Exceeded):
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

N,M = map(int,input().split())
S = input()
T = input()

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(p):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
print(re)

Fixed submission:
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

N,M = map(int,input().split())
S = input()
T = input()

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(0,p,max((p//N),(p//M))):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
			break
print(re)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
a,b,n = 0,0,int(input())
n1 = n//2 + n%2
n2 = n//2
z = list(map(int,input().split()))
a,b = Counter(z[0::2]).most_common(2),Counter(z[1::2]).most_common(2)

if a[0] == b[0]:
	print(n2)
elif len(a) == 1 and len(b) == 1:
    print(int(n/2))
else:
	print(n1 - a[0][1]+n2 - b[0][1])

Fixed submission:
n = int(input())
p = 1110

print(p-n)
Buggy python submission (verdict: Time Limit Exceeded):
st1 = input()
st2 = input()
key1 = list(st1)
key2 = list(st2)

def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)

    return result

result1 = str(list_difference(key1,key2))
result2 = str(list_difference(key2,key1))



def az_count(s):
	ss = []
	ss.append(s.count('a'))
	ss.append(s.count('b'))
	ss.append(s.count('c'))
	ss.append(s.count('d'))
	ss.append(s.count('e'))
	ss.append(s.count('f'))
	ss.append(s.count('h'))
	ss.append(s.count('i'))
	ss.append(s.count('j'))
	ss.append(s.count('k'))
	ss.append(s.count('l'))
	ss.append(s.count('n'))
	ss.append(s.count('m'))
	ss.append(s.count('o'))
	ss.append(s.count('p'))
	ss.append(s.count('q'))
	ss.append(s.count('r'))
	ss.append(s.count('s'))
	ss.append(s.count('t'))
	ss.append(s.count('u'))
	ss.append(s.count('v'))
	ss.append(s.count('w'))
	ss.append(s.count('x'))
	ss.append(s.count('y'))
	ss.append(s.count('z'))
	return ss

t = az_count(result1)
t1 = az_count(result2)

t.sort()
t1.sort()
if t == t1:
	print("Yes")
else:
	print("No")

Fixed submission:


st1 = input()
st2 = input()
key1 = list(st1)
key2 = list(st2)

def az_count(s):
	ss = []
	ss.append(s.count('a'))
	ss.append(s.count('b'))
	ss.append(s.count('c'))
	ss.append(s.count('d'))
	ss.append(s.count('e'))
	ss.append(s.count('f'))
	ss.append(s.count('g'))
	ss.append(s.count('h'))
	ss.append(s.count('i'))
	ss.append(s.count('j'))
	ss.append(s.count('k'))
	ss.append(s.count('l'))
	ss.append(s.count('n'))
	ss.append(s.count('m'))
	ss.append(s.count('o'))
	ss.append(s.count('p'))
	ss.append(s.count('q'))
	ss.append(s.count('r'))
	ss.append(s.count('s'))
	ss.append(s.count('t'))
	ss.append(s.count('u'))
	ss.append(s.count('v'))
	ss.append(s.count('w'))
	ss.append(s.count('x'))
	ss.append(s.count('y'))
	ss.append(s.count('z'))
	return ss

t = az_count(key1)
t1 = az_count(key2)

t.sort()
t1.sort()
if t == t1:
	print("Yes")
else:
	print("No")
Buggy python submission (verdict: Time Limit Exceeded):

from collections import Counter
from collections import defaultdict
from functools import lru_cache
import itertools
import random
import cProfile
import copy

N,M = map(int,input().split())

X = [i for i in range(N+1)]

count = 0
for i in itertools.product(X,X,X):
	if sum(i) == M:
		count += 1
print(count)

Fixed submission:
import itertools

N,M = map(int,input().split())
X = [i for i in range(N+1)]

count = 0
for x,y in itertools.product(X,X):
	if 0 <= M - x - y <= N:
		count += 1

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())

X = [i for i in range(N+1)]
Y = [i for i in range(N+1)]
Z = [i for i in range(N+1)]

count = 0
for x in X:
	for y in Y:
		for z in Z:
			if x+y+z == M :
				#print(x,y,z)
				count += 1
print(count)

Fixed submission:
import itertools

N,M = map(int,input().split())
X = [i for i in range(N+1)]

count = 0
for x,y in itertools.product(X,X):
	if 0 <= M - x - y <= N:
		count += 1

print(count)
Buggy python submission (verdict: Runtime Error):
def solve():
    N = int(input())
    cost = list(map(int, input().split()))
    memo = {}
    def helper(i):
        if i in memo:
            return memo[i]
        if i == 0:
            return 0
        # use i at i+1 or i+2
        if i + 1 < N:
            f = abs(cost[i-1] - cost[i]) + helper(i-1)
        else:
            u1 = abs(cost[i-1] - cost[i]) + helper(i-1)
            u2 = abs(cost[i-2] - cost[i]) + helper(i-2)
            f = min(u1, u2)
        memo[i] = f
        return f
    return helper(N-1)
print(solve())

Fixed submission:
import sys
sys.setrecursionlimit(1000000)
def solve():
    N = int(input())
    cost = list(map(int, input().split()))
    memo = {}
    def helper(i):
        if i in memo:
            return memo[i]
        if i == 0:
            return 0
        # use i at i+1 or i+2
        if i - 2 >= 0:
            u1 = abs(cost[i-1] - cost[i]) + helper(i-1)
            u2 = abs(cost[i-2] - cost[i]) + helper(i-2)
            f = min(u1, u2)
        else:
            f = abs(cost[i-1] - cost[i]) + helper(i-1)
        memo[i] = f
        return f
    return helper(N-1)
print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
a, b, k = [int(i) for i in input().split()]
s1 = {x for x in range(a, b+1) if a + k > x}
s2 = {x for x in range(a, b+1) if b - k < x}
for i in sorted(list(s1 | s2)):
    print(i)


Fixed submission:
a, b, k = [int(i) for i in input().split()]
s = set()
for i in range(a, a+k):
    if i in range(a, b+1):
        s.add(i)

for i in range(b-k+1, b+1):
    if i in range(a, b+1):
        s.add(i)

for i in sorted(list(s)):
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
a, b, k = [int(i) for i in input().split()]
s1 = {x for x in range(a, b+1) if a + k > x}
s2 = {x for x in range(a, b+1) if b - k < x}
for i in sorted(list(s1 | s2)):
    print(i)


Fixed submission:
a, b, k = [int(i) for i in input().split()]
s = set()
for i in range(a, a+k):
    if i in range(a, b+1):
        s.add(i)

for i in range(b-k+1, b+1):
    if i in range(a, b+1):
        s.add(i)

for i in sorted(list(s)):
    print(i)
Buggy python submission (verdict: Runtime Error):
n = int(raw_input())

if n % 2 == 0:
    return n
else:
    return 2*n

Fixed submission:
n = int(raw_input())
 
if n % 2 == 0:
    print n
else:
    print 2*n
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = 0
x = [s += int(i) for i in input().split()]
print(s - n)


Fixed submission:
n = int(input())
x = [int(i) for i in input().split()]
print(sum(x) - n)
Buggy python submission (verdict: Runtime Error):
x = input()
print(x.count('+') - count('-'))

Fixed submission:
x = input()
print(x.count('+') - x.count('-'))
Buggy python submission (verdict: Runtime Error):
import math

n = int(input())
a = []  
  for i in range(n):
    a.append(int(input()))
if n == 1:
  print(a[0])
else:
  lcm = (a[0] * a[1]) // math.gcd(a[0], a[1])
  for i in range(2, n):
    lcm = (lcm * a[i]) // math.gcd(lcm, a[i])
  print(lcm)


Fixed submission:
import math

n = int(input())
a = []  
for i in range(n):
  a.append(int(input()))
if n == 1:
  print(a[0])
else:
  lcm = (a[0] * a[1]) // math.gcd(a[0], a[1])
  for i in range(2, n):
    lcm = (lcm * a[i]) // math.gcd(lcm, a[i])
  print(lcm)

Buggy python submission (verdict: Runtime Error):
import math

n = int(input())
a = []
if n == 1:
  print(a[0])
else:
  
  for i in range(n):
    a.append(int(input()))
  lcm = (a[0] * a[1]) // math.gcd(a[0], a[1])
  for i in range(2, n):
    lcm = (lcm * a[i]) // math.gcd(lcm, a[i])
  print(lcm)


Fixed submission:
import math

n = int(input())
a = []  
for i in range(n):
  a.append(int(input()))
if n == 1:
  print(a[0])
else:
  lcm = (a[0] * a[1]) // math.gcd(a[0], a[1])
  for i in range(2, n):
    lcm = (lcm * a[i]) // math.gcd(lcm, a[i])
  print(lcm)

Buggy python submission (verdict: Runtime Error):
import math

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
lcm = (a[0] * a[1]) // math.gcd(a[0], a[1])
for i in range(2, n):
  lcm = (lcm * a[i]) // math.gcd(lcm, a[i])
print(lcm)


Fixed submission:
import math

n = int(input())
a = []  
for i in range(n):
  a.append(int(input()))
if n == 1:
  print(a[0])
else:
  lcm = (a[0] * a[1]) // math.gcd(a[0], a[1])
  for i in range(2, n):
    lcm = (lcm * a[i]) // math.gcd(lcm, a[i])
  print(lcm)
Buggy python submission (verdict: Runtime Error):
x = 'aeiou'
i = input()
if i in x:
  print("vowel")
else
  print("consonant")

Fixed submission:
x = 'aeiou'
i = input()
if i in x:
  print("vowel")
else:
  print("consonant")
Buggy python submission (verdict: Runtime Error):
from math import gcd
n,x = map(int,input().split())
l = [int(ele) for ele in input().split()]
l.append(x)
l.sort()
g = 0 
for i in range(1,n+1):
    g = gcd(g,l[i]-l[i-1])
print(g)


Fixed submission:
def gcd(a,b):
    if b==0:
        return a 
    return gcd(b,a%b)
n,x = map(int,input().split())
l = [int(ele) for ele in input().split()]
l.append(x)
l.sort()
g = 0 
for i in range(1,n+1):
    g = gcd(g,l[i]-l[i-1])
print(g)
Buggy python submission (verdict: Time Limit Exceeded):
# cook your dish here
# from math import * 
#for _ in range(int(input().strip())):

s = input()
k = int(input())
var = 0
sub = set()

for var in range(97,123):
    if len(sub)>k:
        break
    for i in range(len(s)):
        if s[i]==chr(var):
            for j in range(i,len(s)):
                sub.add(s[i:(j+1)])
l = list(sub)
l.sort()
print(l[k-1])

Fixed submission:
# cook your dish here
# from math import * 
#for _ in range(int(input().strip())):

s = input()
k = int(input())
var = 0
sub = set()
size = 0
for var in range(97,123):
    if len(sub)>k:
        break
    for i in range(len(s)):
        size=0
        if s[i]==chr(var):
            for j in range(i,len(s)):
                if size>=k:
                    break
                sub.add(s[i:(j+1)])
                size+=1 
l = list(sub)
l.sort()
print(l[k-1])
Buggy python submission (verdict: Runtime Error):
from math import * 
def lcm(a,b):
    return (a*b)//gcd(a,b)

ans=1
for _ in range(int(input())):
    ans=lcm(ans,int(input()))
print(ans)

Fixed submission:
#from math import * 
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    return (a*b)//gcd(a,b)

ans=1
for _ in range(int(input())):
    ans=lcm(ans,int(input()))
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import * 
def lcm(a,b):
    return (a*b)//gcd(a,b)

ans=1
for _ in range(int(input())):
    ans=lcm(ans,int(input()))
print(ans)

Fixed submission:
#from math import * 
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    return (a*b)//gcd(a,b)

ans=1
for _ in range(int(input())):
    ans=lcm(ans,int(input()))
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

def dp(i,n,a):
	if i==(n-1):
		return 0
	d1=1e10
	d2=1e10
	if(i+1<=n-1):
		d1=dp(i+1,n,a)+abs(a[i]-a[i+1])
	if(i+2<=n-1):
		d2=dp(i+2,n,a)+abs(a[i]-a[i+2])
	return min(d1,d2)

print(dp(0,n,a))


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

dp = [0]*n
for i in range(1,n):
	if i == 1:
		dp[i]=abs(a[0]-a[1])
	else:
		dp[i]=min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]))
print(dp[n-1])

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

def dp(i,n,a):
	if i==(n-1):
		return 0
	elif i>n-1:
		return 1e9
	d1=1e9
	d2=1e9
	if(i+1<=n-1):
		d1=dp(i+1,n,a)+abs(a[i]-a[i+1])
	if(i+2<=n-1):
		d2=dp(i+2,n,a)+abs(a[i]-a[i+2])
	return min(d1,d2)

print(dp(0,n,a))


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

dp = [0]*n
for i in range(1,n):
	if i == 1:
		dp[i]=abs(a[0]-a[1])
	else:
		dp[i]=min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]))
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[1e9]*(n+k)
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
                dp[i+j]=min(dp[i+j],abs(a[i]-a[i+j])+dp[i])
print(dp[n-1])

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[1e9]*(n+k)
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
                dp[i+j]=min(dp[i+j],abs(a[i]-a[i+j])+dp[i])
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

d={}

def dp(wgt,n): 
    if n==0 or wgt==0: 
        return 0
    if(a[n-1]>wgt):
        if((wgt,n-1) in d):
            return d[(wgt,n-1)] 
        return dp(wgt,n-1) 
    else:
        d1=0
        if (wgt,n-1) in d:
            d1=d[(wgt,n-1)]
        else:
            d1=dp(wgt,n-1)
        d2=0
        if (wgt-a[n-1],n-1) in d:
            d2=d[(wgt-a[n-1],n-1)]
        else:
            d2=dp(wgt-a[n-1],n-1)
        return max(v[n-1]+d2,d1)
print(dp(wgt,n))

Fixed submission:
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

dp=[[0 for x in range(wgt+1)] for x in range(n+1)]

for i in range(n+1):
    for j in range(wgt+1):
        if i==0 or j==0:
            dp[i][j]=0
        elif a[i-1]<=j:
            dp[i][j]=max(v[i-1]+dp[i-1][j-a[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][wgt])

Buggy python submission (verdict: Time Limit Exceeded):
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

def dp(wgt,n): 
    if n==0 or wgt==0: 
        return 0
    if(a[n-1]>wgt): 
        return dp(wgt,n-1) 
    else: 
        return max(v[n-1]+dp(wgt-a[n-1],n-1),dp(wgt,n-1))
print(dp(wgt,n))

Fixed submission:
n,wgt=map(int,input().split())
a=[]
v=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    v.append(y)

dp=[[0 for x in range(wgt+1)] for x in range(n+1)]

for i in range(n+1):
    for j in range(wgt+1):
        if i==0 or j==0:
            dp[i][j]=0
        elif a[i-1]<=j:
            dp[i][j]=max(v[i-1]+dp[i-1][j-a[i-1]],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][wgt])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
d={}
dp={}

for _ in range(m):
	x,y=map(int,input().split())
	try:
		d[x].append(y)
	except:
		d[x]=[y]

def lp(a):
	if a in dp:
		return dp[a]
	if a not in d:
		dp[a]=1
		return 1
	ans=0
	for i in d[a]:
		ans=max(ans,1+lp(i))
	dp[a]=ans
	return ans

print(lp(x))


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

n,m=map(int,input().split())
d={}
dp={}
n=[]

for _ in range(m):
	x,y=map(int,input().split())
	n.append(x)
	try:
		d[x].append(y)
	except:
		d[x]=[y]

def lp(a):
	if a in dp:
		return dp[a]
	if a not in d:
		dp[a]=1
		return 1
	ans=0
	for i in d[a]:
		ans=max(ans,1+lp(i))
	dp[a]=ans
	return ans

p=0
for i in n:
	p=max(p,lp(i))
print(p-1)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
a=[]
dp={}
dp[(h-1,w-1)]=1
for i in range(h):
	a.append(list(input()))

def foo(i,j):
	if i>=h or j>=w:
		return 0
	if (i,j) in dp:
		return dp[(i,j)]
	ans=0
	if i+1<h and a[i+1][j]=='.':
		ans+=foo(i+1,j)
	if j+1<w and a[i][j+1]=='.':
		ans+=foo(i,j+1)
	dp[(i,j)]=ans%(1e9+7)
	return dp[(i,j)]

print(int(foo(0,0)))


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

h,w=map(int,input().split())
a=[]
dp={}
dp[(h-1,w-1)]=1
for i in range(h):
	a.append(list(input()))

def foo(i,j):
	if i>=h or j>=w:
		return 0
	if (i,j) in dp:
		return dp[(i,j)]
	ans=0
	if i+1<h and a[i+1][j]=='.':
		ans+=foo(i+1,j)
	if j+1<w and a[i][j+1]=='.':
		ans+=foo(i,j+1)
	dp[(i,j)]=ans%(1e9+7)
	return dp[(i,j)]

print(int(foo(0,0)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

n=int(input())
a=list(map(float,input().split()))
dp={}

def foo(i,h,t,p):
	if i==n-1:
		if h>t:
			return p
		else:
			return 0
	return foo(i+1,h+1,t,p*a[i+1])+foo(i+1,h,t+1,p*(1-a[i+1]))

print(foo(-1,0,0,1))


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

n=int(input())
a=list(map(float,input().split()))
dp=[[0.0 for _ in range(n+1)] for _ in range(n+1)]
dp[1][1]=a[0]
dp[1][0]=1-a[0]
 
for i in range(2, n+1):
    for j in range(i+1):
        dp[i][j]=a[i - 1] * dp[i - 1][j - 1]+(1 - a[i - 1])*dp[i - 1][j]
 
print(sum(dp[n][n // 2 + 1:]))

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(float,input().split()))
dp={}

def foo(i,h,t,p):
	if i==n-1:
		if h>t:
			return p
		else:
			return 0
	return foo(i+1,h+1,t,p*a[i+1])+foo(i+1,h,t+1,p*(1-a[i+1]))

print(foo(-1,0,0,1))


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

n=int(input())
a=list(map(float,input().split()))
dp=[[0.0 for _ in range(n+1)] for _ in range(n+1)]
dp[1][1]=a[0]
dp[1][0]=1-a[0]
 
for i in range(2, n+1):
    for j in range(i+1):
        dp[i][j]=a[i - 1] * dp[i - 1][j - 1]+(1 - a[i - 1])*dp[i - 1][j]
 
print(sum(dp[n][n // 2 + 1:]))
Buggy python submission (verdict: Runtime Error):
def cost(list, t):
    if t <= 0:
        return 0
    elif t == 1:
        return abs(list[1] - list[0])
    else:
        return min(cost(list, t - 1) + abs(list[t] - list[t - 1]), cost(list, t - 2) + abs(list[t] - list[t - 2]))

n = int(input())
h = input().split(" ")
h = list(map(int, h))
print(cost(h, n - 1))

Fixed submission:
def expand_result(result, h, t):
    if t <= 0:
        result.append(0)
    elif t == 1:
        result.append(abs(h[1] - h[0]))
    else:
        result.append(min(result[t - 1] + abs(h[t] - h[t - 1]), result[t - 2] + abs(h[t] - h[t - 2])))
    return result

n = int(input())
h = input().split(" ")
h = list(map(int, h))
result = []
for i in range(n):
    result = expand_result(result, h, i)
print(result[n - 1])