Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
n = int(input())
s = input()
ans = 0
for p in product([0,1], repeat=2*n):
    if p.count(1) != p.count(0):
        continue
    left = right = ""
    for j in range(2*n):
        if p[j]:
            left += s[j]
        else:
            right += s[j]
    right = right[-1::-1]
    if left == right:
        ans += 1
print(ans)


Fixed submission:
from itertools import product
from collections import defaultdict
n = int(input())
s = input()
sa, sb = s[:n], s[n:][::-1]
a, b, ans = defaultdict(int), defaultdict(int), 0
for p in product(range(2), repeat=n):
    word_a_1, word_b_1, word_a_2, word_b_2 = "", "", "", ""
    for j in range(n):
        if p[j]:
            word_a_1 += sa[j]
            word_b_1 += sb[j]
        else:
            word_a_2 += sa[j]
            word_b_2 += sb[j]
    a[(word_a_1, word_a_2)] += 1
    b[(word_b_1, word_b_2)] += 1
while a:
    key, value = a.popitem()
    ans += value * b[key]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
n = int(input())
s = input()
ans = 0
for p in product([0,1], repeat=2*n):
    left = right = ""
    for j in range(2*n):
        if p[j]:
            left += s[j]
        else:
            right += s[j]
    right = right[-1::-1]
    if left == right:
        ans += 1
print(ans)


Fixed submission:
from itertools import product
from collections import defaultdict
n = int(input())
s = input()
sa, sb = s[:n], s[n:][::-1]
a, b, ans = defaultdict(int), defaultdict(int), 0
for p in product(range(2), repeat=n):
    word_a_1, word_b_1, word_a_2, word_b_2 = "", "", "", ""
    for j in range(n):
        if p[j]:
            word_a_1 += sa[j]
            word_b_1 += sb[j]
        else:
            word_a_2 += sa[j]
            word_b_2 += sb[j]
    a[(word_a_1, word_a_2)] += 1
    b[(word_b_1, word_b_2)] += 1
while a:
    key, value = a.popitem()
    ans += value * b[key]
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
k = int(input())

digsum = lambda x: sum(map(int, list(str(x))))
dignorm = lambda x: x/digsum(x)

n = 1
order = 1
while k > 0:
    print(n)
    k -= 1
    if dignorm(n+10**(order-1)) > dignorm(n+10**order):
        order += 1
    n += 10**(order-1)



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

if n == k:
    print(1)
    exit()

a = (n-k)//(k-1)
if (n-k)%(k-1):
    print(a+2)
else:
    print(a+1)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n, x = map(int, input().split())
d = [tuple(map(int, input().split())) for _ in range(x)]
c = [tuple(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for v in itertools.permutations(list(range(1, x+1)), 3):
    tmp2 = 0
    for i in range(3):
        tmp1 = 0
        j = 0
        k = i
        while k <= 2*n-2:
            for l in range(n):
                if -l + k < 0 or -l + k >= n:
                    continue
                tmp1 += d[c[-l+k][l]-1][v[i]-1]
            j += 1
            k = 3*j+i
        tmp2 += tmp1
    ans = min(ans, tmp2)
print(ans)


Fixed submission:
import itertools
N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]
c = [tuple(map(lambda x: x-1, map(int, input().split()))) for _ in range(N)]

grid = [[0] * C for _ in range(3)]
for i, j in itertools.product(range(N), repeat=2):
    grid[(i+j)%3][c[i][j]] += 1

ans = float("inf")
for color_after in itertools.permutations(range(C), 3):
    s = sum([sum([grid[g][color_before]*D[color_before][color_after[g]] for color_before in range(C)]) for g in range(3)])
    ans = min(ans, s)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
ans = float('inf')
for i in range(n):
    tmp = s[:i].count('W') + s[i+1:].count('E')
    ans = min(ans, tmp)
print(ans)


Fixed submission:
n = int(input())
s = input()
a = s[1:].count('E')
inf = float('inf')
ans = [inf]*n
ans[0] = a
for i in range(1,n):
    if s[i] == 'E':
        ans[i] = ans[i-1] - 1
        if s[i-1] == 'W':
            ans[i] += 1
        else:
            continue
    else:
        ans[i] = ans[i-1]
        if s[i-1] == 'W':
            ans[i] += 1
        else:
            continue
print(min(ans))
Buggy python submission (verdict: Runtime Error):
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, min(i+k,n+1)):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])



Fixed submission:
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, n+1):
        tmp = s[i:j]
        if len(tmp) > k:
            continue
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])



Fixed submission:
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())

n = len(s)

d = [set() for i in range(26)]

for i in range(n):
    for j in range(i+1, n+1):
        tmp = s[i:j]
        d[ord(tmp[0]) - 97].add(tmp)

for i in range(26):
    num = i
    if len(d[i]) >= k:
        break
    else:
        k -= len(d[i])

a = sorted(list(d[num]))
print(a[k-1])



Fixed submission:
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, n+1):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])


Fixed submission:
s = input()
k = int(input())

n = len(s)

d = set()
for i in range(n):
    for j in range(i+1, min(i+k+1,n+1)):
        tmp = s[i:j]
        d.add(tmp)
a = sorted(list(d))
print(a[k-1])
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
p = list(map(lambda x: x-1, map(int, input().split())))
t = [tuple(map(lambda x: x-1, map(int, input().split()))) for _ in range(m)]

a = [set() for _ in range(n)]
for i, j in t:
    a[p[i]].add(p[j])
    a[p[j]].add(p[i])

def dfs(x, v):
    if v[x] == 0:
        v[x] = 1
        for i in a[x]:
            dfs(i, v)

mx = []
for i in range(n):
    v = [0]*n
    dfs(i, v)
    mx.append(v)

ans = 0
for i in range(n):
    tmp = p[i]
    idx = p.index(i)
    if mx[tmp][i]:
        ans += 1
        p[i] = i
        p[idx] = tmp
print(ans)


Fixed submission:
n, m = map(int, input().split())
p = list(map(lambda x: x-1, map(int, input().split())))

follow = [i for i in range(n)]
num = [1]*n
def root_index_of(x):
    r = x
    while follow[r] != r:
        r = follow[r]
    return r

def connected(x, y):
    return root_index_of(x) == root_index_of(y)

def connect(x, y):
    rx = root_index_of(x)
    ry = root_index_of(y)

    if rx == ry:
        return

    if num[rx] < num[ry]:
        follow[rx] = ry
        follow[x] = ry
        num[ry] += num[rx]
    else:
        follow[ry] = rx
        follow[y] = rx
        num[rx] += num[ry]

for i in range(m):
    x, y = map(lambda x: x-1, map(int, input().split()))
    connect(p[x], p[y])

ans = 0
for i in range(n):
    if connected(i, p[i]):
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])
t = list(set(s))
def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for i in t:
    m = s.count(i)
    ans += comb(m, 2)
print(ans)


Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0 for i in range(n+1)]
for i in range(n):
    s[i+1] = s[i] + a[i]
t = list(set(s))

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for i in t:
    m = s.count(i)
    ans += comb(m, 2)
print(ans)


Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(n):
    ans = 0
    for j in range(i, n):
        ans += a[j]
        if ans == 0:
            count += 1
print(count)


Fixed submission:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)
Buggy python submission (verdict: Runtime Error):
n, c = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(n)]

S_cw = [0]
S_ccw = [0]
S_cw_return = [0]
S_ccw_return = [0]

for i in range(n):
    S_cw.append(S_cw[-1]+x[i][1])
    S_ccw.append(S_ccw[-1]+x[n-1-i][1])

for i in range(n):
    S_cw[i+1] -= x[i][0]
    S_ccw[i+1] -= c-x[n-1-i][0]
    S_cw_return.append(S_cw[i+1] - x[i][0])
    S_ccw_return.append(S_ccw[i+1] - (c-x[n-1-i][0]))

S_cw_return_max = [0]
S_ccw_return_max = [0]
for i in range(n):
    if S_cw_return[i+1] > S_cw_return_max[-1]:
        S_cw_return_max.append(S_cw_return[i+1])
    else:
        S_cw_return_max.append(S_cw_return_max[-1])

    if S_ccw_return[i+1] > S_ccw_return_max[-1]:
        S_ccw_return_max.append(S_ccw_return[i+1])
    else:
        S_ccw_return_max.append(S_ccw_return_max[-1])

ans = 0
for i in range(n+1):
    idx = n-i
    ans = max(ans, S_cw[i]+S_ccw_return_max[idx], S_ccw[i]+S_cw_return_max[idx])
print(ans)



Fixed submission:
s = input()
print(700+s.count("o")*100)

Buggy python submission (verdict: Runtime Error):
s = input()
print(700+s.count(o)*100)

Fixed submission:
s = input()
print(700+s.count("o")*100)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
for i in range(n):
    z = y.copy()
    z.remove(x[i])
    print(z[n//2-1])


Fixed submission:
n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
y1, y2 = y[n//2-1], y[n//2]
for i in range(n):
    if x[i] <= y1:
        print(y2)
    else:
        print(y1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = sorted(list(map(int, input().split())))
m = a.pop()

def binary_search(l, value):
    low = 0
    high = len(l)-1
    while low <= high:
        mid = (low + high)//2
        if l[mid] == value:
            print(m, l[mid])
            exit()
        elif l[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return low

k = binary_search(a, m//2)
print(m, a[k])


Fixed submission:
from bisect import bisect_left
n = int(input())
a = sorted(list(map(int, input().split())))
if n == 2:
    print(a[1], a[0])
    exit()
m = a.pop()
idx = bisect_left(a, m//2)
if idx == 0:
    print(m, a[0])
    exit()
else: 
    r1 = a[idx-1]
    r2 = a[idx]

    if r1 > m-r2:
        r = r1
    else:
        r = r2

print(m, r)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
ans = 0
for i in range(a, b+1):
  temp = []
  for j in range(5):
    d = 10**(4-i)
    p = i//d
    temp.append(p)
    i -= p*d
  if temp[0] == temp[4] and temp[1] == temp[3]:
    ans += 1
print(ans)

Fixed submission:
a, b = map(int, input().split())
ans = 0
for i in range(a, b+1):
  temp = []
  for j in range(5):
    d = 10**(4-j)
    p = i//d
    temp.append(p)
    i -= p*d
  if temp[0] == temp[4] and temp[1] == temp[3]:
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ans(n//3)

Fixed submission:
n = int(input())
print(n//3)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = list(map(int, input().split()))
for i in range(n):
  if s[i] == "Y":
    print("Four")
    exit()
print("Three")

Fixed submission:
n = int(input())
s = input().split()
for i in range(n):
  if s[i] == "Y":
    print("Four")
    exit()
print("Three")
Buggy python submission (verdict: Runtime Error):
a,b = map(int, input().split())

if (a*b)%2:
  print("Even")
  else:
    print("Odd")

Fixed submission:
a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")

Buggy python submission (verdict: Runtime Error):
 a,b = map(int, input().split())
  
  if a*b % 2 == 0:
    print("Even")
  else:
    print("Odd")
    
 

Fixed submission:
a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
Buggy python submission (verdict: Runtime Error):
from math import sqrt
a, b = input().split()
n = int(a+b)
if sqrt(n) == int(sqrt(n)):
  print("Yes")
else
  print("No")


Fixed submission:
from math import sqrt
a, b = input().split()
n = int(a+b)
if sqrt(n) == int(sqrt(n)):
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
import Math
a, b = map(int, input().split())
print(Math.ceil((a+b)/2))


Fixed submission:
import math
a, b = map(int, input().split())
print(math.ceil((a+b)/2))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
ans = 0
b = set()
for i in range(n):
    if a[i] in b:
        continue
    else:
        if a.count(a[i]) < a[i]:
            ans += a.count(a[i])
        elif a.count(a[i]) > a[i]:
            ans += a.count(a[i])-a[i]
        b.add(a[i])
print(ans)


Fixed submission:
from collections import Counter
n = int(input())
ans = 0 
c = Counter(list(map(int, input().split())))

for key, value in c.items():
    if key < value:
        ans += value-key
    elif key > value:
        ans += value
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
ans = 0
for i in b:
    if a.count(i) < i:
        ans += a.count(i)
    elif a.count(i) > i:
        ans += a.count(i)-i
    else:
        continue
print(ans)


Fixed submission:
from collections import Counter
n = int(input())
ans = 0 
c = Counter(list(map(int, input().split())))

for key, value in c.items():
    if key < value:
        ans += value-key
    elif key > value:
        ans += value
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
list = input().split()

num_list = []
for c in list:
    n = int(c)
    num_list.append(n)

state = True

i = 0

while state:
    for n in num_list:
        if n % 2:
            state = False
        else:
            n /= 2
    if state:
        i += 1

print(i)


Fixed submission:
print(input().count("1"))
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n, k = map(int, input().split())
c = Counter(list(map(int, input().split()))).most_common()
m = 0
for i in range(k):
    m += c[i][1]
print(n-m)


Fixed submission:
from collections import Counter
n, k = map(int, input().split())
c = Counter(list(map(int, input().split()))).most_common()
l = len(c)
if l >= k:
    m = 0
    for i in range(k):
        m += c[i][1]
    print(n-m)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
h,w = map(int, input().split())
power = [list(map(int,input().split())) for i in range(10)]

#ワーシャルフロイド法
for i in range(10):
    for j in range(10):
        for k in range(10):
            power[j][k] = min([power[j][k], power[j][i] + power[i][k])

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]

print(ans)



Fixed submission:
h,w = map(int, input().split())
power = [list(map(int,input().split())) for i in range(10)]

#ワーシャルフロイド法
for i in range(10):
    for j in range(10):
        for k in range(10):
            power[j][k] = min(power[j][k], power[j][i] + power[i][k])

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]

print(ans)
Buggy python submission (verdict: Runtime Error):
x, y, z = map(int, input().split())
i = 0
while True:
  if x - i*y - (i+1)*z >= 0:
    i += 1
  esle:
    break
print(i-1)


Fixed submission:
x, y, z = map(int, input().split())
i = 0
while x - y*i - z*(i+1) >= 0:
    i += 1
print(i-1)
Buggy python submission (verdict: Runtime Error):
import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
ma = min(a)
b = sorted([x for x in map(int, input().split()) if x > ma])
mb = min(b)
c = sorted([x for x in map(int, input().split()) if x > mb])
m = len(c)
ans = 0
for x in b:
    #挿入できる箇所を返す
    p = bisect.bisect_left(a, x)
    q = m - bisect.bisect_right(c, x)
    ans += p*q
print(ans)


Fixed submission:
import bisect
n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
m = len(c)
ans = 0
for x in b:
    #挿入できる箇所を返す
    p = bisect.bisect_left(a, x)
    q = m - bisect.bisect_right(c, x)
    ans += p*q
print(ans)
Buggy python submission (verdict: Runtime Error):
a = list(map(int, input().split()))
b = set(a)
for x in a:
  if a.count(x) == b.count(x):
    print(x)
    exit()

Fixed submission:
a = list(map(int, input().split()))
for x in a:
  if a.count(x) == 1:
    print(x)
    exit()
Buggy python submission (verdict: Runtime Error):
a, b, c, d, e, f = map(int, input().split())

n = f//(100*a)
m = f//(100*b)
p = f//c
q = f//d

mx = 0
for k in range(p+1):
    for l in range(q+1):
        for i in range(n+1):
            for j in range(m+1):
                if i == 0 and j == 0:
                    continue
                s = 100*a*i+100*b*j
                t = c*k+d*l
                u = 100*t/s
                if s + t> f:
                    continue
                if u > e:
                    continue
                if mx < u:
                    mx = u
                    ans1, ans2 = s+t, t
                    if mx == e:
                        print(ans1, ans2)
                        exit()
print(ans1, ans2)


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

n = f//(100*a)
m = f//(100*b)
p = f//c
q = f//d

mx = 0
state = True
for k in range(p+1):
    for l in range(q+1):
        for i in range(n+1):
            for j in range(m+1):
                if i == 0 and j == 0:
                    continue
                s = 100*a*i+100*b*j
                t = c*k+d*l
                u = 100*t/s
                if s + t> f:
                    continue
                if u > e:
                    continue
                if mx < u:
                    state = False
                    mx = u
                    ans1, ans2 = s+t, t
                    if mx == e:
                        print(ans1, ans2)
                        exit()
if state:
    print(100*a, 0)
else:
    print(ans1, ans2)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [int(input()) for _ in range(n)]

d = []
for i in range(n):
    if a[i] in d:
        d.remove(a[i])
    else:
        d.append(a[i])
print(len(d))


Fixed submission:
from collections import Counter
n = int(input())
a = Counter([int(input()) for _ in range(n)])

ans = 0
for key in a.keys():
    if a[key] % 2:
        ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int, input().split()))
Q = P.copy()
cnt1 = 0
for i in range(N-1):
    if P[i] == i+1:
        tmp = P[i]
        P[i] = P[i+1]
        P[i+1] = tmp
        cnt1 += 1
if P[-1] == N:
    cnt1 += 1

cnt2 = 0
for i in range(N-1, 0, -1):
    if Q[i] == i+1:
        tmp = Q[i]
        Q[i] = Q[i-1]
        Q[i-1] = tmp
        cnt2 += 1
if Q[0] == 1:
    cnt2 += 1
print(min(cnt1, cnt2))


Fixed submission:
x, t = map(int, input().split())
print(max(0, x-t))
Buggy python submission (verdict: Runtime Error):
x, a, b = map(int, input().split())
if abs(x-a) < abs(x-b):
  pirnt("A")
else:
  print("B")

Fixed submission:
x, a, b = map(int, input().split())
if abs(x-a) < abs(x-b):
  print("A")
else:
  print("B")
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

n = int(input())
a = [int(input()) for _ in range(n)]

def lcm_base(x, y):
    return (x*y)//math.gcd(x, y)

def lcm(nums):
    #3つ目は初期値
    return reduce(lcm_base, nums, 1)

print(lcm(a))



Fixed submission:
#import math
from functools import reduce

n = int(input())
a = [int(input()) for _ in range(n)]

def gcd(x, y):
    while y:
        x, y = y, x%y
    return x

def lcm_base(x, y):
    return (x*y)//gcd(x, y)

def lcm(nums):
    #3つ目は初期値
    return reduce(lcm_base, nums, 1)

print(lcm(a))