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

Fixed submission:
# 回答を見て

x = -1
y = -1
S = list(input())

for i in range(len(S)-1):
    if S[i] == S[i+1]:
        x = i+1
        y = x+1
        break
    elif i+2<=len(S)-1:
        if S[i] == S[i+2]:
            x = i+1
            y = x+2
            break
        else:
            pass
    else:
        pass
print(x, y)

Buggy submission (verdict: Runtime Error):
import pandas as pd

x = -1
y = -1
S = list(input())
for i in range(1, len(S)-1):
    for j in range(i+2, len(S)+1):
        s = pd.DataFrame(S[i:j])
        if s[0].value_counts()[0] > (len(s)//2):
            x = i
            y = j
            break
print(x, y)
Problem p04045 (python)

Fixed submission:
N, K = map(int, input().split())
D = list(map(str, input().split()))
num_set = set(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'])
N_list = list(str(N))

diff_list = sorted(list(num_set.difference(set(D))))

if (list(set(D)&set(N_list)) == []):
    print(N)
else:
    if '0' in diff_list:
        n_list = [diff_list[1]] + ['0']*len(N_list)
    else:
        n_list = [diff_list[0]]*(len(N_list)+1)
    str_n = ''
    for i in n_list:
        str_n += str(i)
    new_n = int(str_n)+1
    for ii in range(N, new_n):
        if list(set(list(str(ii)))&set(D)) == []:
            print(ii)
            break

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
D = list(map(str, input().split()))
num_set = set(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'])
N_list = list(str(N))

diff_list = sorted(list(num_set.difference(set(D))))

if (list(set(D)&set(N_list)) == []):
    print(N)
else:
    if '0' in diff_list:
        n_list = [diff_list[1]] + ['0']*len(N_list)
    else:
        n_list = [diff_list[0]]*len(N_list+1)
    str_n = ''
    for i in n_list:
        str_n += str(i)
    new_n = int(str_n)+1
    for ii in range(N, new_n):
        if list(set(list(str(ii)))&set(D)) == []:
            print(ii)
            break
Problem p02642 (python)

Fixed submission:
import numpy as np

N = int(input())
A = list(map(int, input().split(" ")))
Amax = max(A)
dp = np.ones(Amax, dtype=bool)
appear = np.zeros(Amax, dtype=int)
for a in A:
  appear[a-1] += 1

for i in range(1, len(dp)+1):
  if not dp[i-1]:
    continue
  if appear[i-1] != 0:
    j = 2
    while j * i <= Amax:
      dp[j * i - 1] = False
      j += 1
# print(dp)

app_set = set([])
dup_set = set([])
count = 0
for a in A:
  if appear[a-1] > 1:
    continue
  else:
    count += dp[a-1]
print(count -  len(dup_set))

Buggy submission (verdict: Runtime Error):
import numpy as np

N = int(input())
A = [int(x) for x in input().split(" ")]
Amax = max(A)
dp = np.ones(Amax, dtype=bool)
appear = np.zeros(Amax, dtype=int)
for a in A:
  appear[a-1] += 1

for i in range(1, len(dp)+1):
  if not dp[i-1]:
    continue
  if appear[i-1] != 0:
    j = 2
    while j * i <= Amax:
      dp[j * i - 1] = False
      j += 1

count = 0
for a in A:
  if appear[a-1] > 1:
    continue
  else:
    count += dp[a-1]
print(count -  len(dup_set))
Problem p02646 (python)

Fixed submission:
A, V = map(int, input().split(" "))
B, W = map(int, input().split(" "))
T = int(input())

if W > V:
  print("NO")
else:

  if abs(A - B) <= T * (V - W):
    print("YES")
  else:
    print("NO")

# if A - B > 0:
#   # 負の方向に逃げる
#   if (B + 10**9) / W <= T:
#     # print("left reach")
#     # T立つよりも先に端に到達してしまう場合
#     Bdist = (B + 10**9)
#   else:
#     # print("run left")
#     Bdist = W * T
# else:
#   # 正の方向に逃げる
#   if (10**9 - B) / W <= T:
#     # print("right reach")
#     Bdist = (10**9 - B)
#   else:
#     # print("run right")
#     Bdist = W * T

# Adist = V * T
# if Bdist + abs(A - B) <= Adist:
#   print("YES")
# else:
#   print("NO")

Buggy submission (verdict: Runtime Error):
A, V = map(int, input().split(" "))
B, W = map(int, input().split(" "))
T = int(input())

if W > V:
  print("NO")
else:
  if abs(A - B) / (V - W) <= T:
    print("YES")
  else:
    print("NO")
Problem p02678 (python)

Fixed submission:
import numpy as np
N, M = map(int, input().split(" "))

goto = {i: [] for i in range(1, N+1)}
sign = np.zeros(N, dtype=int)
for _ in range(M):
  A, B = map(int, input().split(" "))
  goto[A].append(B)
  goto[B].append(A)

# print(goto)

visited = set([1])
queue = [1]
while len(queue) > 0:
  v = queue.pop(0)
  for nex in goto[v]:
    if nex in visited:
      continue
    sign[nex-1] = v
    queue.append(nex)
    visited.add(nex)
print("Yes")
for s in sign[1:]:
  print(s)

Buggy submission (verdict: Runtime Error):
# import heapq
import numpy as np

N, M = [int(x) for x in input()]

e = {i: [] for i in range(N)}
for _ in range(M):
  a, b = [int(x)-1 for x in input()]
  e[a].append(b)
  e[b].append(a)

d = np.ones(N, dtype=int) * -1

q = [0]
while len(q) != 0:
  v = q.pop(0)
  for ne in e[v]:
    if d[ne] == -1:
      d[ne] = v
      q.append(ne)

print("Yes")
# for p in prev[1:]:
#   print(p+1)
print("\n".join([str(p+1) for p in d[1:]]))

Buggy submission (verdict: Runtime Error):
import heapq
import numpy as np

N, M = [int(x) for x in input().split(" ")]

e = {i: [] for i in range(N)}
for _ in range(M):
  a, b = [int(x)-1 for x in input().split(" ")]
  e[a] = e[a] + [b]
  e[b] = e[b] + [a]

# roots = [[int(x) for x in input().split(" ")] for _ in range(M)]

d = np.ones(N, dtype=int) * -1
# prev = np.ones(N, dtype=int) * -1
# q = [(d[0], 0)]
# heapq.heapify(q)

# while len(q) != 0:
#   c, u = heapq.heappop(q)
#   for nv in e[u]:
#     alt = d[u] + 1
#     if d[nv] > alt:
#       d[nv] = alt
#       prev[nv] = u
#       heapq.heappush(q, (alt, nv))

q = [d[0]]
while len(q) != 0:
  v = q.pop(0)
  for ne in e[v]:
    if d[ne] == -1:
      d[ne] = v
    q.append(ne)

print("Yes")
# for p in prev[1:]:
#   print(p+1)
print("\n".join([str(p+1) for p in d[1:]]))
Problem p02717 (python)

Fixed submission:
a,b,c =map(int,input().split())

print(c , end= " ")
print(a , end= " ")
print(b)

Buggy submission (verdict: Runtime Error):
a,b,c = int(input())

print(c , end= " ")
print(a , end= " ")
print(b)
Problem p02719 (python)

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

if(n%k == 0):
        
    g = n//k
        
    print(n - (g*k))
else:
    g = n//k
    ans = n - (g*k)
    if(abs(ans - k) < ans):
        print(abs(ans - k))
    else:
        print(ans)

Buggy submission (verdict: Runtime Error):

n,k = map(int,input().split())

d = abs(n-k)

print(n % d)
Problem p02639 (python)

Fixed submission:
a = list(map(int, input().split()))
print(sum(range(1, 5 + 1)) - sum(a))

Buggy submission (verdict: Runtime Error):
a = list(map(int, input()))
print(sum(range(1, 5 + 1)) - sum(a))
Problem p02697 (python)

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

if n % 2: # odd
    for i in range(m):
        print(i + 1, n - i)
else: # even
    for i in range(m):
        if 1 + 2 * i >= n - 1 - 2 * i:
            l1 = i
            break
        m -= 1
        print(i + 1, n - i)

    for i in range(m):
        if i + 1 + l1 >= n - i - l1 - 1:
            raise Exception()
        print(i + 1 + l1, n - i - l1 - 1)

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

if n % 2: # odd
    raise Exception()
    for i in range(n // 2):
        print(i + 1, n - i)
else: # even
    a = [True] * n
    cnt = 1
    for i in range(n):
        if i + cnt >= n:
            break
        if a[i]:
            print(i + 1, i + 1 + cnt)
            a[i + cnt] = False
            cnt += 1
Problem p02698 (python)

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

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

graph = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    graph[u].append(v)
    graph[v].append(u)

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node, length=0):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    length = max(p + 1, length)
    for child in rooted[node]:
        dfs(child, length)
    table[p] = old
    lis[node] = length

dfs(0)
print(*map(str, lis), sep="\n")

Buggy submission (verdict: Runtime Error):
import bisect

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

graph = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    graph[u].append(v)
    graph[v].append(u)

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    for child in rooted[node]:
        dfs(child)
    table[p] = old
    lis[node] = p + 1

dfs(0)
print(*map(str, lis), sep="\n")
Problem p02934 (python)

Fixed submission:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
print(1 / np.sum(1 / a))

Buggy submission (verdict: Runtime Error):
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
print(1 / np.sum(1 / a))
Problem p02936 (python)

Fixed submission:
from collections import deque
n, q = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    # print(a, b)

nodes = [0 for _ in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    nodes[p] += x

# print(nodes)
result = [0 for _ in range(n + 1)]

# que = [(1, nodes[1])]
que = deque([(1, nodes[1])])

visited = [False] * (n + 1)
while que:
    i, cost = que.popleft()
    if visited[i]:
        continue
    result[i] = cost
    visited[i] = True
    for sub in graph[i]:
        que.append((sub, cost + nodes[sub]))
print(*result[1:])

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

graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    # print(a, b)

nodes = [0 for _ in range(n + 1)]
for i in range(q):
    p, x = map(int, input().split())
    nodes[p] += x

# print(nodes)
result = [0 for _ in range(n + 1)]
def dfs(i=1, cost=nodes[1]):
    result[i] = cost
    for sub in graph[i]:
        dfs(sub, cost + nodes[sub])
dfs()
print(*result[1:])
Problem p02982 (python)

Fixed submission:
import itertools
import numpy as np
n, d = map(int, input().split())

points = [list(map(int, input().split())) for x in range(n)]

cnt = 0
for p1, p2 in itertools.combinations(points, r=2):
    d = np.linalg.norm(np.array(p1) - p2)
    if d == int(d):
        cnt += 1
print(cnt)

Buggy submission (verdict: Runtime Error):
import itertools
import numpy as np
n, d = map(int, input().split())

points = [list(map(int, input().split())) for x in range(n)]

cnt = 0
for p1, p2 in itertools.combinations(points, r=2):
    d = np.linalg.norm(np.array(p1) - p2)
    if d == int(d):
        cnt += 1
print(cnt)
Problem p02997 (python)

Fixed submission:
import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print("1\n1 2" if k == 0 else -1)

Buggy submission (verdict: Runtime Error):
import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= (n - 1) * (n - 2) // 2:
#         return -1
# if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
import itertools
from tqdm import tqdm
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= (n - 1) * (n - 2) // 2:
#         return -1
# if n > 2 and k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
import itertools
n, k = map(int, input().split())

def c(n):
    if n <= 2:
        return 1
    return n * (n - 1) // 2


if k <= c(n - 1):
    print(n - 1 + c(n - 1) - k)
    nodes = list(range(2, n + 1))
    for i in nodes:
        print(1, i)

    combi = itertools.combinations(nodes, 2)
    for i in range(c(n - 1) - k):
        print(*next(combi))
else:
    print(-1)
Problem p03032 (python)

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

results = []
for a in range(n + 1):
    for b in range(min(n - a, k - a) + 1):
        p = v[:a] + v[n - b:]
        p.sort()
        for i in range(k - a - b + 1):
            results.append(sum(p[i:]))
print(max(results))

Buggy submission (verdict: Runtime Error):
import numpy as np
n, k = map(int, input().split())
v = list(map(int, input().split()))

left = np.cumsum([0] + v)
right = np.cumsum([0] + v[::-1])

results = []
for backn in range(k + 1):
    at = k - backn

    t = min(n, at)
    # print('----', backn, t)
    for shift in range(t + 1):
        p = v[:t - shift] + v[n - shift:]
        # print(v[:t - shift], v[n - shift:])
        p.sort()
        value = sum(p[backn:])
        results.append(value)
print(max(max(results)), 0)
Problem p03112 (python)

Fixed submission:
import bisect
import math
a, b, q = map(int, input().split())
inf = float("inf")
s = [-inf] + [int(input()) for _ in range(a)] + [inf]
t = [-inf] + [int(input()) for _ in range(b)] + [inf]

results = ""
for _ in range(q):
    x = int(input())
    si = bisect.bisect_right(s, x)
    spos = [s[si], s[si - 1]]

    ti = bisect.bisect_right(t, x)
    tpos = [t[ti], t[ti - 1]]

    result = float("inf")
    for svalue in spos:
        for tvalue in tpos:
            if svalue == tvalue == inf or svalue == tvalue == -inf:
                continue
            result = min(
                abs(x - svalue) + abs(svalue - tvalue),
                abs(x - tvalue) + abs(tvalue - svalue),
                result
            )

    results += str(result) + "\n"
print(results)

Buggy submission (verdict: Runtime Error):
import math
a, b, q = map(int, input().split())
s = [-float("inf")] + [int(input()) for _ in range(a)] + [float("inf")]
t = [-float("inf")] + [int(input()) for _ in range(b)] + [float("inf")]

s.sort()
t.sort()

def near(x, buildings):
    left, right = 0, len(buildings) - 1

    while right - left > 1:
        center = (left + right) // 2
        value = buildings[center]
        if x < value:
            right = center
        elif x > value:
            left = center
        else:
            return center
    return left if abs(x - buildings[left]) < abs(x - buildings[right]) else right


for _ in range(q):
    near(x, s)
    near(x, t)
#     x = int(input())
# 
#     si = near(x, s)
#     spos = [si, si + 1] if s[si] < x else [si, si - 1]
#     ti = near(x, t)
#     tpos = [ti, ti + 1] if t[ti] < x else [ti, ti - 1]
# 
#     result = float("inf")
#     for sindex in spos:
#         for tindex in tpos:
#             v1 = abs(x - s[sindex]) + abs(s[sindex] - t[tindex])
#             v2 = abs(x - t[tindex]) + abs(t[tindex] - s[sindex])
#             result = min(
#                 float("inf") if math.isnan(v1) else v1,
#                 float("inf") if math.isnan(v2) else v2,
#                 result
#             )
# 
#     print(result)
Problem p03160 (python)

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


def diff(now, d):
    return abs(a[now] - a[now - d])

# dp = [None] * n
# def dfs(depth=n - 1):
#     if dp[depth] != None:
#         return dp[depth]
#     if depth == 0:
#         dp[depth] = 0
#         return 0
#     if depth == 1:
#         dp[depth] = dfs(depth=depth - 1) + diff(depth, 1)
#         return dp[depth]
#     dp[depth] = min(dfs(depth=depth - 1) + diff(depth, 1), dfs(depth=depth - 2) + diff(depth, 2))
#     return dp[depth]
#
# print(dfs())

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
print(dp[-1])

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

def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [None] * n
def dfs(depth=n - 1):
    if dp[depth] != None:
        return dp[depth]
    if depth == 0:
        dp[depth] = 0
        return 0
    if depth == 1:
        dp[depth] = dfs(depth=depth - 1) + diff(depth, 1)
        return dp[depth]
    dp[depth] = min(dfs(depth=depth - 1) + diff(depth, 1), dfs(depth=depth - 2) + diff(depth, 2))
    return dp[depth]


print(dfs())
Problem p03161 (python)

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


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])

Buggy submission (verdict: Runtime Error):
import numpy as np
n, k = map(int, input().split())
a = list(map(int, input().split()))


def diff(now, d):
    return abs(a[now] - a[now - d])

dp = [0] * n
dp[1] = diff(1, 1)
for depth in range(2, n):
    # dp[depth] = min(dp[depth - 1] + diff(depth, 1), dp[depth - 2] + diff(depth, 2))
    dp[depth] = min(dp[depth - x] + diff(depth, x) for x in range(1, min(depth, k) + 1))
print(dp[-1])
Problem p03163 (python)

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [[None] * (10**5 + 1) for _ in range(100 + 1)]
# def dfs(weight=0, depth=N - 1):
#     if dp[depth][weight] is not None:
#         return dp[depth][weight]
#
#     if depth == -1:
#         dp[depth][weight] = 0
#         return 0
#
#     if weight + ws[depth] <= W:
#         result = max(dfs(weight, depth - 1), dfs(weight + ws[depth], depth - 1) + vs[depth])
#     else:
#         result = dfs(weight, depth - 1)
#     dp[depth][weight] = result
#     return result
#
# print(dfs())

dp[-1] = [0] * len(dp[-1])
for depth in range(0, N):
    for weight in range(10**5 + 1):
        v = dp[depth - 1][weight]
        if weight + ws[depth] <= W:
            dp[depth][weight] = max(v, dp[depth - 1][weight + ws[depth]] + vs[depth])
        else:
            dp[depth][weight] = v

print(dp[N - 1][0])

Buggy submission (verdict: Runtime Error):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [[None] * 10**5 for _ in range(100)]
def dfs(weight=0, depth=N - 1):
    if dp[weight][depth] is not None:
        return dp[weight][depth]

    if depth == -1:
        return 0

    if weight + ws[depth] <= W:
        result = max(dfs(weight + ws[depth], depth - 1) + vs[depth], dfs(weight, depth - 1))
    else:
        result = dfs(weight, depth - 1)
    dp[weight][depth] = result
    return result

print(dfs())
Problem p03167 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]

dp = [[None] * w for _ in range(h)]
def dfs(hindex=h - 1, windex=w - 1):
    if field[hindex][windex] == "#":
        return 0
    if hindex == windex == 0:
        return 1

    if dp[hindex][windex] is not None:
        return dp[hindex][windex]
    r = (hindex and dfs(hindex - 1, windex)) + (windex and dfs(hindex, windex - 1))
    dp[hindex][windex] = r
    return r

print(dfs() % (10**9 + 7))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())

field = [list(input()) for _ in range(h)]

dp = [[None] * w for _ in range(h)]
def dfs(hindex=h - 1, windex=w - 1):
    if field[hindex][windex] == "#":
        return 0
    if hindex == windex == 0:
        return 1

    if dp[hindex][windex] is not None:
        return dp[hindex][windex]
    r = (hindex and dfs(hindex - 1, windex)) + (windex and dfs(hindex, windex - 1))
    dp[hindex][windex] = r
    return r

print(dfs() % (10**9 + 7))
Problem p03168 (python)

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

import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(n=half, depth=n - 1):
    if depth < 0 or (n - 1) > depth:
        return 0

    if dp[n][depth] is not None:
        return dp[n][depth]

    if n == 0:
        r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
    elif (n - 1) == depth:
        r = functools.reduce(operator.mul, p[:depth + 1])
    else:
        r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
    dp[n][depth] = r
    return r

print(sum(dfs(i) for i in range(half, n + 1)))

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

dp = [[None] * 1501 for i in range(3000)]
def dfs(i=0, at=(n + 1) // 2):
    if i == n:
        return int(at <= 0)
    if dp[i][at] is not None:
        return dp[i][at]

    r = dfs(i + 1, at - 1) * a[i] + dfs(i + 1, at) * (1 - a[i])
    dp[i][at] = r
    return r

print(dfs())

Buggy submission (verdict: Runtime Error):
import functools
import operator
n = int(input())
p = list(map(float, input().split()))
half = n // 2 + 1

dp = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(n=half, depth=n - 1):
    if depth < 0 or (n - 1) > depth:
        return 0

    if dp[n][depth] is not None:
        return dp[n][depth]

    if n == 0:
        r = functools.reduce(operator.mul, map(lambda x: 1 - x, p[:depth + 1]))
    elif (n - 1) == depth:
        r = functools.reduce(operator.mul, p[:depth + 1])
    else:
        r = dfs(n - 1, depth - 1) * p[depth] + dfs(n, depth - 1) * (1 - p[depth])
    dp[n][depth] = r
    return r

print(sum(dfs(i) for i in range(half, n + 1)))