Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,A,B,C,D=map(int, raw_input().split())
S=raw_input()

if C<D:
	if "##"  in S[B-1:D]:
		print "No"
		quit()
	if "##" in S[A-1:C]:
		print "No"
		quit()
	print "Yes"
elif D<C:
	if "##" in S[A-1:C]:
		print "No"
		quit()

	for i in range(B-1,D):
		if S[i]==S[i+1]==S[i+2]==".":
			print "Yes"
			quit()

	print "No"

Fixed submission:
N,A,B,C,D=map(int, raw_input().split())
S=raw_input()

if C<D:
	if "##"  in S[B-1:D]:
		print "No"
		quit()
	if "##" in S[A-1:C]:
		print "No"
		quit()
	print "Yes"
elif D<C:
	if "##" in S[A-1:C]:
		print "No"
		quit()

	if "..." in S[B-2:D+1]:
		print "Yes"
		quit()
	print "No"
Buggy python submission (verdict: Time Limit Exceeded):
s=raw_input()
l=len(s)

str=""
i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		ans+=cnt
	else:
		str+="X"
		i+=1
		cnt=0


print ans

Fixed submission:
s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans

Buggy python submission (verdict: Time Limit Exceeded):
s=raw_input()
l=len(s)

str=""
i=0
LSUM=[0]
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt=LSUM[-1]+1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		cnt=LSUM[-1]
		ans+=cnt
	else:
		str+="X"
		i+=1
		cnt=0
	LSUM.append( cnt )


print ans

Fixed submission:
s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans

Buggy python submission (verdict: Time Limit Exceeded):
s=raw_input()
l=len(s)

str=""
i=0
LSUM=[0]
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt=LSUM[-1]+1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		cnt=LSUM[-1]
		ans+=cnt
	else:
		str+="X"
		i+=1
		cnt=0
	LSUM.append( cnt )

LSUM=LSUM[1:]

ans=0
for i,x in enumerate(str):
	if x=="D":
		ans+=LSUM[i]

print ans

Fixed submission:
s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans

Buggy python submission (verdict: Time Limit Exceeded):
s=raw_input()
l=len(s)

str=""
i=0
LSUM=[0]
cnt=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt=LSUM[-1]+1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		cnt=LSUM[-1]
	else:
		str+="X"
		i+=1
		cnt=0
	LSUM.append( cnt )

LSUM=LSUM[1:]

ans=0
for i,x in enumerate(str):
	if x=="D":
		ans+=LSUM[i]

print ans

Fixed submission:
s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans
Buggy python submission (verdict: Time Limit Exceeded):
N,A,B,C=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 2*N):
	fact_tmp *= i
	fact_tmp %= mod
	fact.append(fact_tmp)
	inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


P=0
for g in range(N, 2*N):
	P+=100**(2*N-1-g) * g*(A**N)*(B**(g-N))*ncr(g-1,(N-1))
	P%=mod
	P+=100**(2*N-1-g) * g*(A**(g-N))*(B**N)*ncr(g-1,(N-1))
	P%=mod

Q=pow( 100 , 2*N-1 ,mod)

if C>0: P,Q=Q,P
print ( P*pow(Q, mod-2 , mod) ) % mod

Fixed submission:
N,A,B,C=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 2*N):
	fact_tmp *= i
	fact_tmp %= mod
	fact.append(fact_tmp)
	inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


P=0
for g in range(N, 2*N):
	P+=pow( A+B , (2*N-1-g) , mod) * g*pow(A,N,mod)* pow(B,g-N,mod) *ncr(g-1,(N-1))
	P%=mod
	P+=pow( A+B , (2*N-1-g) ,mod) * g*pow(A,g-N,mod) * pow(B,N,mod) *ncr(g-1,(N-1))
	P%=mod

Q=pow( A+B , 2*N-1,mod) 

hikiwake=100*pow(100-C,mod-2, mod) 
print ( P*pow(Q, mod-2 , mod) *hikiwake )%mod
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product, combinations
N,M,K=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N*M+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


torisuu=ncr(N*M-2,K-2)
Zahyou=list( product(range(N), range(M)) )
Combi=list( combinations( range(N*M), 2) )


ans=0
for first, second in Combi:
	unit_cost=abs( Zahyou[second][0]-Zahyou[first][0] ) + abs(Zahyou[second][1]-Zahyou[first][1])
	unit_cost%=mod
	ans+=unit_cost*torisuu
	ans%=mod

print ans

Fixed submission:
from itertools import product, combinations
N,M,K=map(int, raw_input().split())


mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N*M+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


torisuu=ncr(N*M-2,K-2)

ans=0
for i in range(N):
	for j in range(M):
		l_sum=(1+j)*j/2*N		#left
		r_sum=(1+(M-j-1))*(M-j-1)/2*N	#right	
		u_sum=(1+i)*i/2*M		#upper
		d_sum=(1+(N-i-1))*(N-i-1)/2*M	#down
		ans+=(l_sum+r_sum+u_sum+d_sum)*torisuu
		ans%=mod

print ( ans*pow(2,mod-2,mod) ) %mod
Buggy python submission (verdict: Runtime Error):
N,K=map(int, raw_input().split())
S=raw_input()

if "0" not in S:
	print len(S)
	quit()

L=[]
zero_kukan=0
for i,x in enumerate(S):
	if i==0:
		cnt=1
		if x=="0": zero_kukan+=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
			if x=="0": zero_kukan+=1
	prev=x
else:
	L.append(cnt)

K=min(K, zero_kukan)


LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)


#print "L :::: ",L
#print "LSUM  :::: ",LSUM

lsum_len=len(LSUM)

#print "lsum_len  :::: ",lsum_len

h=2*K+1

ans=0
if S[0]=="1":
	for l in range(0,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
else:
	ans=max(ans, LSUM[2*K]-LSUM[0])
	for l in range(1,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
	
	ans=max(ans, LSUM[lsum_len-1]-LSUM[lsum_len-1-2*K])
print ans
		

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

if "0" not in S:
	print len(S)
	quit()
L=[]
if S[0]=="0": L.append(0)
for i,x in enumerate(S):
	if i==0:
		cnt=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
	prev=x
else:
	L.append(cnt)

if S[-1]=="0": L.append(0)

LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)

K=min(K,len(L)/2)

ans=0
len_lsum=len(LSUM)
for l in range(0,len_lsum,2):
	r=l+2*K+1
	if r < len_lsum:
		ans=max(ans , LSUM[r]-LSUM[l])

print ans

Buggy python submission (verdict: Runtime Error):
N,K=map(int, raw_input().split())
S=raw_input()

if "0" not in S:
	print len(S)
	quit()

L=[]
for i,x in enumerate(S):
	if i==0:
		cnt=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
	prev=x
else:
	L.append(cnt)	


LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)


#print "L :::: ",L
#print "LSUM  :::: ",LSUM

lsum_len=len(LSUM)

#print "lsum_len  :::: ",lsum_len

h=2*K+1

ans=0
if S[0]=="1":
	for l in range(0,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
else:
	ans=max(ans, LSUM[2*K]-LSUM[0])
	for l in range(1,lsum_len-h,2):
		r=l+h
		ans=max(ans, LSUM[r]-LSUM[l])
	
	ans=max(ans, LSUM[lsum_len-1]-LSUM[lsum_len-1-2*K])
print ans
		

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

if "0" not in S:
	print len(S)
	quit()
L=[]
if S[0]=="0": L.append(0)
for i,x in enumerate(S):
	if i==0:
		cnt=1
	else:
		if prev==x:
			cnt+=1
		else:
			L.append(cnt)
			cnt=1
	prev=x
else:
	L.append(cnt)

if S[-1]=="0": L.append(0)

LSUM=[0]
for x in L:
	LSUM.append(LSUM[-1]+x)

K=min(K,len(L)/2)

ans=0
len_lsum=len(LSUM)
for l in range(0,len_lsum,2):
	r=l+2*K+1
	if r < len_lsum:
		ans=max(ans , LSUM[r]-LSUM[l])

print ans
Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict

N,M=map(int, sys.stdin.readline().split())
A=[ map(int, sys.stdin.readline().split()) for i  in range(M) ] 

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

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

def root(x):
	if par[x]==x:
		return x
	else:
		par[x]=root( par[x] )
		return par[x]

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y
	size[y]+=size[x]

def getsize(x):
	return size[root(x)]


ans=N*(N-1)/2

L=[]

for a,b in reversed(A):
	L.append(max(0,ans))
	if root(a)==root(b):
		n1=getsize(a)
		ans+=n1*(n1-1)/2	
	else:
		n1=getsize(a)
		n2=getsize(b)
		ans+=n1*(n1-1)/2
		ans+=n2*(n2-1)/2

	unite(a,b)

	n=getsize(a)
	ans-=n*(n-1)/2



for x in reversed(L):
	print x


Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

N,M=map(int, sys.stdin.readline().split())
A=[ map(int, sys.stdin.readline().split()) for i  in range(M) ] 

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

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

def root(x):
	if par[x]==x:
		return x
	else:
		par[x]=root( par[x] )
		return par[x]

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y
	size[y]+=size[x]

def getsize(x):
	return size[root(x)]


ans=N*(N-1)/2

L=[]

for a,b in reversed(A):
	L.append(max(0,ans))
	if root(a)==root(b):
		n1=getsize(a)
		ans+=n1*(n1-1)/2	
	else:
		n1=getsize(a)
		n2=getsize(b)
		ans+=n1*(n1-1)/2
		ans+=n2*(n2-1)/2

	unite(a,b)

	n=getsize(a)
	ans-=n*(n-1)/2



for x in reversed(L):
	print x
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import itertools

A,B,Q=map(int, sys.stdin.readline().split())

S=[  int(sys.stdin.readline()) for i in range(A) ]
T=[  int(sys.stdin.readline()) for i in range(B) ]
X=[  int(sys.stdin.readline()) for i in range(Q) ]


for x in X:
	sx=bisect_left(S, x)
	tx=bisect_left(T, x)

	s_temp=[]
	if sx==0:
		s_temp.append(S[sx])	
	elif 0<sx<A:
		s_temp.append(S[sx-1])
		s_temp.append(S[sx])
	else:
		s_temp.append(S[sx-1] )


	t_temp=[]
	if tx==0:
		t_temp.append(T[tx])	
	elif 0<tx<A:
		t_temp.append(T[tx-1])
		t_temp.append(T[tx])
	else:
		t_temp.append(T[tx-1] )


	ans=float("inf")

	for s in s_temp:
		for t in t_temp:
			ans=min(ans, abs(s-x)+abs(s-t) )

	for t in t_temp:
		for s in s_temp:	
			ans=min(ans, abs(t-x)+abs(s-t) )

	print ans
		

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
import itertools

A,B,Q=map(int, sys.stdin.readline().split())

S=[  int(sys.stdin.readline()) for i in range(A) ]
T=[  int(sys.stdin.readline()) for i in range(B) ]
X=[  int(sys.stdin.readline()) for i in range(Q) ]


for x in X:
	sx=bisect_left(S, x)
	tx=bisect_left(T, x)

	s_temp=[]
	if sx==0:
		s_temp.append(S[sx])	
	elif 0<sx<A:
		s_temp.append(S[sx-1])
		s_temp.append(S[sx])
	else:
		s_temp.append(S[sx-1] )


	t_temp=[]
	if tx==0:
		t_temp.append(T[tx])	
	elif 0<tx<B:
		t_temp.append(T[tx-1])
		t_temp.append(T[tx])
	else:
		t_temp.append(T[tx-1] )


	ans=float("inf")

	for s in s_temp:
		for t in t_temp:
			ans=min(ans, abs(s-x)+abs(s-t) )

	for t in t_temp:
		for s in s_temp:	
			ans=min(ans, abs(t-x)+abs(s-t) )

	print ans
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(30,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break


C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数

for a in A:
	for k in range(keta,-1,-1):
	#	print k, x>>k, (x>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


for idx, i in enumerate(C):
	if i<=N/2:
		X+=2**idx	#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる

ans=0
for a in A:
	ans+=X^a

print ans

Fixed submission:
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(50,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break



C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数


for a in A:
	for k in range(keta-1,-1,-1):
		#print "k, a>>k, (a>>k)&1 ::::: ",k, a>>k, (a>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


len_c=len(C)

for i in range(len_c-1,-1,-1):
	ci=C[i]
	if  C[i]<(N+1)/2:
		if X+2**i<=K:
			X+=2**i		#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる
					#1と0が同数の場合は、その桁を0にしたほうが、Xが小さくなるので有利

ans=0
for a in A:
	ans+=X^a

print ans

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(15,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break


C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数

for a in A:
	for k in range(keta,-1,-1):
	#	print k, x>>k, (x>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


for idx, i in enumerate(C):
	if i<=N/2:
		X+=2**idx	#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる

ans=0
for a in A:
	ans+=X^a

print ans

Fixed submission:
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

keta=0

for i in range(50,-1,-1):
	if (K>>i)&1:
		keta=i+1
		break



C=[ 0 for i in range(keta) ]	#桁ごとのbit 1の出現回数


for a in A:
	for k in range(keta-1,-1,-1):
		#print "k, a>>k, (a>>k)&1 ::::: ",k, a>>k, (a>>k)&1
		if (a>>k)&1:		#その桁のbitが1なら、出現回数に+1
			C[k]+=1



X=0	# f(x)が最大となるX


len_c=len(C)

for i in range(len_c-1,-1,-1):
	ci=C[i]
	if  C[i]<(N+1)/2:
		if X+2**i<=K:
			X+=2**i		#桁ごとに見て、ゼロの数が多ければ、f(x)が最大となるXとなるXのidx番目の桁は1になる
					#1と0が同数の場合は、その桁を0にしたほうが、Xが小さくなるので有利

ans=0
for a in A:
	ans+=X^a

print ans
Buggy python submission (verdict: Runtime Error):
import sys

N,K=map(int, sys.stdin.readline().split()) 
T=[ map(int, sys.stdin.readline().split()) for i in range(N) ]
T=sorted(T, key=lambda x:(x[0],-x[1]))

KI=[]	#KIND
A=[]	#Nokori

x=None
for t,d in T:
	if t != x:
		KI.append(d)
		x=t
	else:
		A.append(d)

KI.sort(reverse=True)
A.sort(reverse=True)

KI_S=[0]		#KI Ruiseki sum
A_S=[0]		#A Ruiseki sum

for x in KI: KI_S.append( KI_S[-1]+x )
for x in A:  A_S.append( A_S[-1]+x )


l=len(A_S)

ans=0
for k in range(1,K+1):
	if K-k<l:
		ans=max (ans , KI_S[k]+k**2+A_S[K-k] )

print ans


Fixed submission:
import sys

N,K=map(int, sys.stdin.readline().split()) 
T=[ map(int, sys.stdin.readline().split()) for i in range(N) ]
T=sorted(T, key=lambda x:(x[0],-x[1]))

KI=[]	#KIND
A=[]	#Nokori

x=None
for t,d in T:
	if t != x:
		KI.append(d)
		x=t
	else:
		A.append(d)

KI.sort(reverse=True)
A.sort(reverse=True)

KI_S=[0]		#KI Ruiseki sum
A_S=[0]		#A Ruiseki sum

for x in KI: KI_S.append( KI_S[-1]+x )
for x in A:  A_S.append( A_S[-1]+x )


la=len(A_S)
lk=len(KI_S)

ans=0
for k in range(1,K+1):
	if K-k<la and k<lk:
		ans=max (ans , KI_S[k]+k**2+A_S[K-k] )

print ans
Buggy python submission (verdict: Time Limit Exceeded):
N=input()
H=map(int, raw_input().split())

dp=[ float("inf") for i in range(N) ] 
dp[0]=0

for k in range(N-1):
	for i in range(N,-1,-1):
		if i+2<N:dp[i+2]=min(dp[i+2], dp[i]+ abs( H[i]-H[i+2] )  )
		if i+1<N: dp[i+1]=min(dp[i+1], dp[i]+ abs( H[i]-H[i+1] )  )

print dp[N-1]


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

dp=[ float("inf") for i in range(N) ] 
dp[0]=0

for i in range(N-1):
	if i+2<N:dp[i+2]=min(dp[i+2], dp[i]+ abs( H[i]-H[i+2] )  )
	if i+1<N: dp[i+1]=min(dp[i+1], dp[i]+ abs( H[i]-H[i+1] )  )

print dp[N-1]
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

N,M=map(int, sys.stdin.readline().split())

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, sys.stdin.readline().split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)

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

N,M=map(int, sys.stdin.readline().split())

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

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)


memo={}

def depth(n):
	if n in memo: return memo[n]
	ret=0
	if len( nl[n] )==0:
		return 0
	else:
		for x in nl[n]:
			ret=max(ret, depth(x)+1)
	memo[n]=ret
	return ret


ans=0
for i in range(1,N+1):
	ans=max( ans , depth(i) )

print ans

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

N,M=map(int, sys.stdin.readline()..split())

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, sys.stdin.readline()..split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)

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

N,M=map(int, sys.stdin.readline().split())

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

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)


memo={}

def depth(n):
	if n in memo: return memo[n]
	ret=0
	if len( nl[n] )==0:
		return 0
	else:
		for x in nl[n]:
			ret=max(ret, depth(x)+1)
	memo[n]=ret
	return ret


ans=0
for i in range(1,N+1):
	ans=max( ans , depth(i) )

print ans

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

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

nl=[ [] for i in range(N+1) ] 
f=[ 0 for i in range(N+1) ]
dp=[ 0 for i in range(N+1) ]

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)
	f[y]=1

start=[]
for i in range(1,N+1):
	if f[i]==0:
		start.append(i)


def dfs(v):
	for u in nl[v]:
		dp[u]=max( dp[u], dp[v]+1)
		dfs(u)


for s in start:
	dfs(s)

print max(dp)

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

N,M=map(int, sys.stdin.readline().split())

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

for i in range(M):
	x,y=map(int, raw_input().split())
	nl[x].append(y)


memo={}

def depth(n):
	if n in memo: return memo[n]
	ret=0
	if len( nl[n] )==0:
		return 0
	else:
		for x in nl[n]:
			ret=max(ret, depth(x)+1)
	memo[n]=ret
	return ret


ans=0
for i in range(1,N+1):
	ans=max( ans , depth(i) )

print ans
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int, raw_input().split())

H=[]
for i in range(N):
	h=input()
	H.append(h)

H.sort()

ans=float("inf")
for i in range(N-K+1):
	ans=min( ans, H[i+K-1]-H[i] )

print ans

Fixed submission:
import sys
N,K=map(int, raw_input().split())

H=[]
for i in range(N):
	h=int( sys.stdin.readline() ) 
	H.append(h)

H.sort()

ans=float("inf")
for i in range(N-K+1):
	ans=min( ans, H[i+K-1]-H[i] )

print ans
Buggy python submission (verdict: Runtime Error):
N,X=map(int, raw_input().split())

p=[1]
a=[1]
for i in range(N):
	p.append( p[-1]*2+1 )
	a.append( a[-1]*2+3 )

#print "p:::",p
#print "a::::",a

X-=1

ans=0
def f(N,X):
	global ans
#	print "f (",N ," , ", X ," ) " ,ans

	if N==0:
		if X>=-1:
			return 1
		else:
			return 0
	elif X>=a[N]/2:
		X-=(a[N-1]+2)
		ans+=p[N-1]+1
		f(N-1,X)
	elif X<a[N]/2:
		X-=(a[N-1]+2)
		ans+=f(N-1,X)

	X-=(a[1]+2)

f(N,X)

print ans


Fixed submission:
N,X=map(int, raw_input().split())

a,p=[1], [1]
for i in range(N):
	a.append(a[-1]*2+3)
	p.append(p[-1]*2+1)

def f(N,X):
	if N==0:
		return 0 if X<=0 else 1
	elif X<=1 + a[N-1]:
		return f(N-1,X-1)
	else:
		return p[N-1]+1+f(N-1, X-2-a[N-1])

print f(N,X)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import itertools
from  bisect import bisect_left, bisect_right

N=input()

Parts=defaultdict(lambda: 0)

for i in range(1,N+1):
	num_sqrt=int(i**0.5)+2

	for n in range(2,num_sqrt):
		while i%n==0:
			i/=n
			Parts[n]+=1
	else:
		if i!=1:
			Parts[i]+=1

T=[0,2,4,14,24,74]


L=[]
for x in Parts.values():
	bi=bisect_right(T,x)
	L.append( T[:bi] )
	

K=list(itertools.product(*L))	#Kouho

ans=0
for x in K:
	multiple=1
	for v in x:
		multiple*=(v+1)
	if multiple==75:
		ans+=1


print ans

Fixed submission:
import math
from collections import defaultdict

N=input()

C=defaultdict(lambda: 0)

#L=(2,3,5,7)
L=range(2,101)


for i in range(N,0,-1):
	for l in L:
		while i%l==0:
			i/=l
			C[l]+=1

D=defaultdict(lambda: 0)

for x,y in C.items():
	if y>=4:	D[4]+=1
	if y>=2:	D[2]+=1
	if y>=24:D[24]+=1
	if y>=14:D[14]+=1
	if y>=74:D[74]+=1

ans=0

ans+=D[4]*(D[4]-1)/2*(D[2]-2)
ans+=D[24]*(D[2]-1)
ans+=D[14]*(D[4]-1)
ans+=D[74]
print ans

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import itertools

N=input()

Parts=defaultdict(lambda: 0)

for i in range(1,N+1):
	num_sqrt=int(i**0.5)+2

	for n in range(2,num_sqrt):
		while i%n==0:
			i/=n
			Parts[n]+=1
	else:
		if i!=1:
			Parts[i]+=1

L=[]
for x in Parts.values():
	L.append( range(x+1) )


K=list(itertools.product(*L))	#Kouho

ans=0
for x in K:
	multiple=1
	for v in x:
		multiple*=(v+1)
	if multiple==75:
		ans+=1


print ans

Fixed submission:
import math
from collections import defaultdict

N=input()

C=defaultdict(lambda: 0)

#L=(2,3,5,7)
L=range(2,101)


for i in range(N,0,-1):
	for l in L:
		while i%l==0:
			i/=l
			C[l]+=1

D=defaultdict(lambda: 0)

for x,y in C.items():
	if y>=4:	D[4]+=1
	if y>=2:	D[2]+=1
	if y>=24:D[24]+=1
	if y>=14:D[14]+=1
	if y>=74:D[74]+=1

ans=0

ans+=D[4]*(D[4]-1)/2*(D[2]-2)
ans+=D[24]*(D[2]-1)
ans+=D[14]*(D[4]-1)
ans+=D[74]
print ans