Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]


def contain(l):
    phase = 0
    for c in S:
        if phase == 0 and c == l[0]:
            phase = 1
            continue
        if phase == 1 and c == l[1]:
            phase = 2
            continue
        if phase == 2 and c == l[2]:
            return 1
    return 0


print(sum(list(map(contain, L))))


Fixed submission:
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]
count = 0
for l in L:
    try:
        i = S.index(l[0])
        j = S.index(l[1], i + 1)
        k = S.index(l[2], j + 1)
        count += 1
    except:
        continue
print(count)

Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]


def contain(l):
    phase = 0
    for c in S:
        if phase == 0 and c == l[0]:
            phase = 1
            continue
        if phase == 1 and c == l[1]:
            phase = 2
            continue
        if phase == 2 and c == l[2]:
            return 1
    return 0


f = np.frompyfunc(contain, 1, 1)
print(sum(f(L)))


Fixed submission:
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]
count = 0
for l in L:
    try:
        i = S.index(l[0])
        j = S.index(l[1], i + 1)
        k = S.index(l[2], j + 1)
        count += 1
    except:
        continue
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
count = 0
for A in range(1000):
    x = str(A).zfill(3)[0]
    y = str(A).zfill(3)[1]
    z = str(A).zfill(3)[2]
    phase = 0
    for c in S:
        if phase == 0 and c == str(x):
            phase = 1
            continue
        if phase == 1 and c == str(y):
            phase = 2
            continue
        if phase == 2 and c == str(z):
            count += 1
            break
print(count)


Fixed submission:
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]
count = 0
for l in L:
    try:
        i = S.index(l[0])
        j = S.index(l[1], i + 1)
        k = S.index(l[2], j + 1)
        count += 1
    except:
        continue
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
count = 0
for x in range(10):
    for y in range(10):
        for z in range(10):
            phase = 0
            for c in S:
                if phase == 0 and c == str(x):
                    phase = 1
                    continue
                if phase == 1 and c == str(y):
                    phase = 2
                    continue
                if phase == 2 and c == str(z):
                    count += 1
                    break
print(count)


Fixed submission:
N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]
count = 0
for l in L:
    try:
        i = S.index(l[0])
        j = S.index(l[1], i + 1)
        k = S.index(l[2], j + 1)
        count += 1
    except:
        continue
print(count)
Buggy python submission (verdict: Runtime Error):
mod = 10**9+7

X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = (X + Y) // 3
    r = X - n
    # nCr
    fact = [1, 1]
    for i in range(2, n+1):
        fact.append(fact[-1] * i % mod)
    ans = fact[n]*pow(fact[r], mod-2, mod)*pow(fact[n-r], mod-2, mod) % mod

print(ans)


Fixed submission:
mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    return g1[n] * g2[r] * g2[n-r] % mod


X, Y = map(int, input().split())

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = (X + Y) // 3
    r = min(X, Y) - n
    ans = cmb(n, r, mod)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

def judge(x):
    res=K
    for n in range(N):
        over=max(A[n]*F[n]-x,0)
        res-=-(-over//F[n])
    return res>=0

left=-1
right=10**12*+1
while left+1<right:
    mid=(left+right)//2
    if judge(mid):
        right=mid
    else:
        left=mid
print(right)

Fixed submission:
import numpy as np

N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

A=np.array(A)
F=np.array(F)

def judge(x):
    over=np.maximum(A*F-x,0)
    shug=-(-over//F).sum()
    return shug<=K

left=-1
right=10**12*+1
while left+1<right:
    mid=(left+right)//2
    if judge(mid):
        right=mid
    else:
        left=mid
print(right)

Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

def judge(x):
    res=K
    for n in range(N):
        over=max(A[n]*F[n]-x,0)
        res-=-(-over//F[n])
    return res>=0

def bin_search(left,right):
    if left+1==right:
        return right
    else:
        mid=(left+right)//2
        if judge(mid):
            return bin_search(left,mid)
        else:
            return bin_search(mid,right)
print(bin_search(-1,10**12+1))

Fixed submission:
import numpy as np

N,K=map(int,input().split())
A=list(map(int,input().split()))
F=list(map(int,input().split()))
A.sort()
F.sort(reverse=True)

A=np.array(A)
F=np.array(F)

def judge(x):
    over=np.maximum(A*F-x,0)
    shug=-(-over//F).sum()
    return shug<=K

left=-1
right=10**12*+1
while left+1<right:
    mid=(left+right)//2
    if judge(mid):
        right=mid
    else:
        left=mid
print(right)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
*L, = map(int, input().split())
L.sort()
cnt = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        l = max(j+1, bisect.bisect_left(L, b-a))
        r = bisect.bisect_left(L, b+a)
        cnt += r-l
print(cnt)


Fixed submission:
import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
count=0
for i in range(N-2):
    for j in range(i+1,N-1):
        a=L[i]
        b=L[j]
        count+=bisect.bisect_left(L,a+b)-(j+1)
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
C=list(Counter(A).values())
C.sort()

def ans(C,k):
    if C==[]:
        return 0
    elif sum(C)>=k*C[-1]:
        return sum(C)//k
    else:
        return ans(C[:-1],k-1)


for k in range(1,N+1):
    print(ans(C,k))

Fixed submission:
from collections import Counter
import bisect
N=int(input())
A=list(map(int,input().split()))
C=list(Counter(A).values())
C.sort()
L=len(C)

# Cのうちx以上のものの個数D[x]を計算(x=0,...,N)
D=[L-bisect.bisect_left(C,x) for x in range(N+1)]
S=[0]
for n in range(1,N+1):
    S.append(S[-1]+D[n])

# T[x]=S[x]/x(x=1,...,N)としてKをbisect_rightで挿入した時のindexが答え
T=[x/S[x] for x in range(1,N+1)]
for K in range(1,N+1):
    print(bisect.bisect_right(T,1/K))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N,M=map(int,input().split())
A=deque([int(_) for _ in input().split()])

for m in range(M):
    a=max(A)
    A.remove(a)
    A.append(a//2)
print(sum(A))

Fixed submission:
import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

print(-sum(A))

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

N,M=map(int,input().split())
A=[int(_) for _ in input().split()]

for m in range(M):
    a=max(A)
    A.remove(a)
    A.append(a//2)
print(sum(A))

Fixed submission:
import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

print(-sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from collections import deque

N,M=map(int,input().split())
A=[int(_) for _ in input().split()]
A.sort()
A=deque(A)

for m in range(M):
    a=A.pop()//2
    insert_index = bisect.bisect(A,a)
    A=list(A)
    A.insert(insert_index,a)
    A=deque(A)
print(sum(A))

Fixed submission:
import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

print(-sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N,M=map(int,input().split())
A=[int(_) for _ in input().split()]
A.sort()
for m in range(M):
    a=A.pop(-1)//2
    insert_index = bisect.bisect_right(A,a)
    A[insert_index:insert_index]=[a]
print(sum(A))


Fixed submission:
import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

print(-sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N,M=map(int,input().split())
A=[int(_) for _ in input().split()]
A.sort()

for m in range(M):
    a=A.pop(-1)//2
    insert_index = bisect.bisect_right(A,a)
    A.insert(insert_index,a)

print(sum(A))

Fixed submission:
import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

print(-sum(A))
Buggy python submission (verdict: Runtime Error):
N=int(input())
H=list(map(int,input().split()))
count=0
H0=[]
for n in range(N-1):
    right=H[-(n+1)]
    left=H[-(n+2)]
    if left>=right:
        count+=1
        H0=[count]+H0
    else:
        count=0
        H0=[count]+H0

print(max(H0))

Fixed submission:
N=int(input())
H=list(map(int,input().split()))
count=0
maxcount=0
for n in range(N-1):
    right=H[-(n+1)]
    left=H[-(n+2)]
    if left>=right:
        count+=1
    else:
        count=0
    if count>maxcount:
        maxcount=count

print(maxcount)
Buggy python submission (verdict: Runtime Error):
N=int(input())
H=list(map(int,input().split()))
answer='Yes'
for i in range(N-1):
    if H[N-1-i]>=H[N-2-i]:
        answer='Yes'
    elif H[N-1-i]+1==H[N-2-i]:
        H[N-2-i]-=1
    else:
        answer='No'
    print(H)
print(answer)

Fixed submission:
N=int(input())
H=list(map(int,input().split()))
answer='Yes'
for i in range(N-1):
    left=H[N-2-i]
    right=H[N-1-i]
    if left<=right and answer=='Yes':
        answer='Yes'
    elif left==right+1 and answer=='Yes':
        H[N-2-i]-=1
    else:
        answer='No'
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
c = 0
X = []
for a in A:
    i = bisect.bisect_left(X, a)
    if i == 0:
        X.reverse()
        X.append(a)
        X.reverse()
    else:
        X[i-1] = a
print(len(X))


Fixed submission:
import bisect
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
X = []
for a in A:
    i = bisect.bisect_right(X, -a)
    if i == len(X):
        X.append(-a)
    else:
        X[i] = -a
print(len(X))
Buggy python submission (verdict: Runtime Error):
import collections
N=int(input())
a=list(map(int,input().split()))
def judge(a):
    if sum(a)==0:
        return True
    else:
        a=dict(collections.Counter(a))
        a0=list(a.keys())[0]
        a1=list(a.keys())[1]
        a2=list(a.keys())[2]
        if a0^a1==a2:
            return True
    return False

if judge(a):
    print("Yes")
else:
    print("No")

Fixed submission:
import collections
N=int(input())
a=list(map(int,input().split()))
def judge(a):
    if sum(a)==0:
        return True
    else:
        a=dict(collections.Counter(a))
        if len(a.keys())==3:
            a0=list(a.keys())[0]
            a1=list(a.keys())[1]
            a2=list(a.keys())[2]
            if a0^a1==a2 and a[a0]==a[a1] and a[a1]==a[a2]:
                return True
        if len(a.keys())==2:
            a0=list(a.keys())[0]
            a1=list(a.keys())[1]
            if a0==0 or a1==0:
                if a[a0]==2*a[a1] or a[a1]==2*a[a0]:
                    return True
    return False

if judge(a):
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(_) for _ in input().split()]
X=[]
for i in range(N):
    x=0
    for j in range(N):
        if ((j-i)%N)%2==0:
            x+=A[j]
        else:
            x-=A[j]
    X.append(x)
print(' '.join(map(str, X)))

Fixed submission:
N=int(input())
A=[int(_) for _ in input().split()]
X=[]
x=0
for j in range(N):
    if (j%N)%2==0:
        x+=A[j]
    else:
        x-=A[j]
X.append(x)
for i in range(1,N):
    x=2*A[i-1]-X[i-1]
    X.append(x)
print(' '.join(map(str, X)))
Buggy python submission (verdict: Time Limit Exceeded):
def BC2D(s):
    n=len(s)
    index=[]
    for i in range(n-1):
        if s[i:i+2]=='BC':
            index.append(i)
    new_s=''
    for i in range(n):
        if i in index:
            new_s+='D'
        elif i-1 in index:
            new_s+=''
        else:
            new_s+=s[i]
    return new_s

def partition(s):
    s='B'+s+'C'
    group=[]
    n=len(s)
    left=0
    right=0
    for i in range(n-1):
        block=s[i:i+2]
        if block[0] in ['B','C'] and block[1] in ['A','D']:
            left=i
        if block[0] in ['A','D'] and block[1] in ['B','C']:
            right=i
            group.append(s[left:right+1])
    return group

def turningNo(s):
    totalCount=0
    count=0
    n=len(s)
    s=s[::-1]
    for i in range(n):
        if s[i]=='A':
            totalCount+=count
        if s[i]=='D':
            count+=1
    return totalCount

s=input()
s=BC2D(s)
G=partition(s)
answer=0
for element in G:
    answer+=turningNo(element)
print(answer)

Fixed submission:
s=input()
s=s.replace("BC","D")
totalCount=0
count=0
for char in s:
    if char=="A":
        count+=1
    elif char=="D":
        totalCount+=count
    else:
        count=0
print(totalCount)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
l0, r0 = 1, n
for j in range(m):
    l1, r1 = map(int, inp)
    l0 = max(l0, l1)
    r0 = min(r0, r1)
print(max(0, r0-l0+1))


Fixed submission:
N,M=map(int,input().split())
L=[]
R=[]
for m in range(M):
    Lm,Rm=map(int,input().split())
    L.append(Lm)
    R.append(Rm)
maxL=max(L)
minR=min(R)
print(max(minR-maxL+1,0))

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
passable=set(range(1,N+1))
for m in range(M):
    L,R=map(int,input().split())
    passable=passable&set(range(L,R+1))
print(len(passable))

Fixed submission:
N,M=map(int,input().split())
L=[]
R=[]
for m in range(M):
    Lm,Rm=map(int,input().split())
    L.append(Lm)
    R.append(Rm)
maxL=max(L)
minR=min(R)
print(max(minR-maxL+1,0))
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(N-1):
    L=L+[gcd(L[-1],A[i])]
    R=[gcd(R[0],A[N-i-1])]+R
M=[gcd(L[n],R[n]) for n in range(N)]
print(max(M))

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N=int(input())
A=list(map(int,input().split()))
x=A[0]
y=A[1]
D=sorted(list(set(make_divisors(x))|set(make_divisors(y))))[::-1]
for d in D:
    if sum([a%d==0 for a in A])>=N-1:
        break
print(d)

Buggy python submission (verdict: Runtime Error):
import math
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(N-1):
    L=L+[math.gcd(L[-1],A[i])]
    R=[math.gcd(R[0],A[N-i-1])]+R
M=[math.gcd(L[n],R[n]) for n in range(N)]
print(max(M))

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N=int(input())
A=list(map(int,input().split()))
x=A[0]
y=A[1]
D=sorted(list(set(make_divisors(x))|set(make_divisors(y))))[::-1]
for d in D:
    if sum([a%d==0 for a in A])>=N-1:
        break
print(d)
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
if A < C < B or B < C < A:
    print("Yes")
else:
    print("No")

Fixed submission:
A, B, C = map(int, input().split())
if A < C < B or B < C < A:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
A,B=map(int,input().split())
C=0
for n in range(A,B+1):
    C^=n
print(C)

Fixed submission:
A,B=map(int,input().split())
def f(n):
    if n%4==0:
        return n
    if n%4==1:
        return 1
    if n%4==2:
        return 1^n
    if n%4==3:
        return 0
print(f(A-1)^f(B))
Buggy python submission (verdict: Runtime Error):
A,B,C=map(int,input().split())
print(min(int(B/A),C)

Fixed submission:
A,B,C=map(int,input().split())
print(min(int(B/A),C))
Buggy python submission (verdict: Runtime Error):
import sympy
def gcd(LIST):
    ans=LIST[0]
    for member in LIST[1:]:
        ans=sympy.gcd(ans,member)
    return ans
N=int(input())
A=list(map(int,input().split()))
print(gcd(A))

Fixed submission:
def gcd(LIST):
    ans=LIST[0]
    for member in LIST[1:]:
        x=max(ans,member)
        y=min(ans,member)
        if x%y==0:
            ans=y
        else:
            while x%y!=0:
                z=x%y
                x=y
                y=z
            ans=z
    return ans
N=int(input())
A=list(map(int,input().split()))
print(gcd(A))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
K = 2
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])


Fixed submission:
N = int(input())
h = list(map(int, input().split()))
dp = [10 ** 10] * N
# dp[n]はあとnのところからのN-1に行くのに支払うコストの最小値
dp[0] = 0
dp[1] = abs(h[N-1]-h[N-2])
for n in range(0, N-2):
    dp[n+2] = min(dp[n+1]+abs(h[(N-1)-(n+2)]-h[(N-1)-(n+1)]),
                  dp[n]+abs(h[(N-1)-(n+2)]-h[(N-1)-n]))
print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
*H, = map(int, input().split())
DP = [0 for i in range(n)]
for i in range(1, n):
    DP[i] = min([DP[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(i, k)+1)])
print(DP[n-1])


Fixed submission:
N, K = map(int, input().split())
K = min(N, K)
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
*H, = map(int, input().split())
X = [0]
for i in range(1, n):
    x = 1 << 30
    for j in range(1, k+1):
        if i-j >= 0:
            x = min(x, X[i-j]+abs(H[i]-H[i-j]))
    X.append(x)
print(X[n-1])


Fixed submission:
N, K = map(int, input().split())
K = min(N, K)
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])


Fixed submission:
N, K = map(int, input().split())
K = min(N, K)
*h, = map(int, input().split())
a = [abs(h[0] - h[k]) for k in range(K)]
for n in range(N - K):
    a = a[1:] + [min([a[k] + abs(h[n + k] - h[n + K]) for k in range(K)])]
print(a[K - 1])
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))


Fixed submission:
n, m = map(int, input().split())
G = [[] for i in range(n)]
I = [0 for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    I[y-1] += 1
# Q:出発点の候補
Q = [i for i in range(n) if I[i] == 0]
# L[i]=iを終点とする最長パスの長さ
L = [0 for i in range(n)]
while Q:
    i = Q.pop()
    while G[i]:
        j = G[i].pop()
        I[j] -= 1
        L[j] = max(L[j], L[i]+1)
        if I[j] == 0:
            Q.append(j)
print(max(L))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
*P, = map(float, input().split())
DP = [[0.0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1.0
for i in range(1, n+1):
    DP[i][0] = DP[i-1][0]*(1-P[i-1])
    for j in range(1, n+1):
        DP[i][j] = DP[i-1][j]*(1-P[i-1])+DP[i-1][j-1]*P[i-1]
print(sum(DP[n][(n+1)//2:]))


Fixed submission:
n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))


Fixed submission:
n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
*P, = map(float, input().split())
# DP[i][j]=i枚中j枚が表の確率
DP = [[0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        DP[i][j] = DP[i-1][j]*(1-P[i-1])+DP[i-1][j-1]*P[i-1]
print(sum(DP[n][(n+1)//2:]))


Fixed submission:
n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))
Buggy python submission (verdict: Runtime Error):
def f(k):
    if k < 0:
        return True
    if k == 0:
        return False
    return any([not f(k-a) for a in A])


n, k = map(int, input().split())
*A, = map(int, input().split())
print(f(k))


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
DP = [False] * (k+1)
for i in range(k+1):
    for a in A:
        if i+a <= k and not DP[i]:
            DP[i+a] = True
if DP[k]:
    print('First')
else:
    print('Second')