Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
S = input()
ans = set({})
lid = list(range(N))

# print(lid)
for p in combinations(lid, 3):
    ss = '_'.join([S[i] for i in lid if i in p])
    # print(p, ss)
    ans.add(ss)
print(len(ans))

Fixed submission:
from itertools import combinations

N = int(input())
S = input()
count = 0

ans = set({})

for password in range(0, 1000):
    s = "{:03d}".format(password)
    s1, s2, s3 = s
    
    if s1 not in S:
        continue
    i1 = S.index(s1)
    if s2 not in S[i1+1:]:
        continue
    i2 = S[i1+1:].index(s2)
    if s3 not in S[i1+1:][i2+1:]:
        continue
    i3 = S[i1+1:][i2+1:].index(s3)
    # print(s, s1, s2, s3, "|", i1, i1 + i2, i1 + i2 + i3)
    ans.add(password)

print(len(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
count = 0
for x in range(1, n):
  for y in range(x + 1, n):
    if x + y == n:
      count += 1
print(count)

Fixed submission:
n = int(input())

if n % 2 == 0:
  print(n // 2 - 1)
else:
  print((n - 1) // 2)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
count = 0

while len(S) > 0:
    i = 0
    si = S[i]
    j = i + 1
    while j < len(S) and si == S[j]:
        j += 1
    S = S[j:]
    count += 1

print(count)

Fixed submission:
N = int(input())
S = input()
count = 0

S += "#"
for i in range(N):
    if S[i] != S[i + 1]:
        count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

# from math import gcd
import fractions

A, B = list(map(int, input().split()))

if A >= B:
    A, B = B, A

# 小さい方の約数リストを計算
divA = []
for i in range(1, A // 2 + 1):
    if A % i == 0:
        divA.append(i)
divA.append(A)
div = [n for n in divA if B % n == 0]
Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
def dfs(i, S, d):
    selected = div[i]
    S.add(selected)
    depth = d
    for j in range(i + 1, Ndiv):
        if fractions.gcd(div[i], div[j]) == 1:
            flag = True
            for k in S:
                if fractions.gcd(k, div[j]) != 1:
                    flag = False
                    break
            if flag:
                dj = dfs(j, S, d + 1)
                depth = max(depth, dj)
    return depth

ans = dfs(0, set({}), 1)
print(ans)

Fixed submission:
import math
from itertools import combinations
from collections import defaultdict

# from math import gcd
import fractions

A, B = list(map(int, input().split()))

def make_prime_list(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def prime_factorization(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        dict_counter = defaultdict(int)
        for prime in prime_list:
            while num % prime == 0:
                dict_counter[prime] += 1
                num //= prime
        if num != 1:
            dict_counter[num] += 1

        dict_counter = dict(dict_counter)

        return dict_counter

if A >= B:
    A, B = B, A

# # 小さい方の約数リストを計算
# divA = []
# for i in range(1, A // 2 + 1):
#     if A % i == 0:
#         divA.append(i)
# divA.append(A)
# div = [n for n in divA if B % n == 0]
# Ndiv = len(div)

# print(div)
# for n in div:
#     for m in div:
#         if n < m and fractions.gcd(n, m) == 1:
#             print(n, m)

# 深さ優先探索
# def dfs(i, S, d):
#     selected = div[i]
#     S.add(selected)
#     depth = d
#     for j in range(i + 1, Ndiv):
#         if fractions.gcd(div[i], div[j]) == 1:
#             flag = True
#             for k in S:
#                 if fractions.gcd(k, div[j]) != 1:
#                     flag = False
#                     break
#             if flag:
#                 dj = dfs(j, S, d + 1)
#                 depth = max(depth, dj)
#     return depth

# ans = dfs(0, set({}), 1)
# print(Ndiv + 1)

lA = prime_factorization(A)
lB = prime_factorization(B)

if not lA or not lB:
    print(1)
    exit()

count = 0
for key in lA:
    if key in lB:
        count += 1
print(count + 1)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()

# stored = set({})
prev = ''

ans = 0
while len(S) > 0:
    j = 1
    while S[:j] == prev:
        j += 1

    if S[:j] == S[j:]:
        j += 1

    prev = S[:j]
    ans += 1
    # stored.add(S[:j])
    # print(j, S[:j], S[j:])
    S = S[j:]

# print(len(stored))
print(ans)

Fixed submission:
S = input()

i = 1
buf = S[0]
ans = 1

while i <= len(S) - 1:
    if buf == S[i]:
        # 2文字ずらすと，何をとってもOK (Siは2文字，Si+1は1文字なので)
        i = i + 2
        if i <= len(S): # ズラした分，末尾じゃなければ+1
            ans += 1
        buf = ""
    else:
        # 違う文字ならそのまま入れ替えればOK
        ans += 1
        buf = S[i]
        i = i + 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 解説を読んでからrun-length

S = input()

# build run-length
Srl = []
SS = ''
i = 0
while i < len(S):
    j = i
    while j < len(S) and S[i] == S[j]:
        j += 1
    SS += "{}{}".format(S[i], j - i)
    Srl.append((S[i], j - i))
    i = j

def solve(nR, nL):
    s = "{}{}".format('R' * nR, 'L' * nL)
    # print(nR, nL, s)

    # 10^100は偶数ステップ
    # 協会のRの位置: nR - 1 (ここから偶数ステップ)
    # 協会のLの位置: nR (ここから偶数ステップ)

    idxR = [k for k in range(nR - 1, nR + nL, 2)]
    idxL = [k for k in range(nR, nR + nL, 2)]
    for i in range(nR):
        if i in idxR or i in idxL:
            continue
        if i not in idxR and (i - (nR - 1)) % 2 == 0:
            idxR.append(i)
        elif i not in idxL:
            idxL.append(i)

    numR = len(idxR)
    numL = len(idxL)
    ans = [0] * (nR + nL)
    ans[nR - 1] = numR
    ans[nR] = numL
    return ans

ans_all = []
for i in range(0, len(Srl), 2):
    ans = solve(Srl[i][1], Srl[i + 1][1])
    ans_all += ans

print(*ans_all)

Fixed submission:
# 解説を読んでからrun-length
# TLEだったので見て修正

import bisect

S = input()
RL = []
for i in range(len(S) - 1):
    if S[i] == 'R' and S[i + 1] == 'L':
        RL.append(i)


ans = [0] * len(S)
for i in range(len(S)):
    idx = bisect.bisect_left(RL, i)
    if S[i] == 'L':  # Lだと見つかった場所の←へ行く
        mark = RL[idx - 1]
    else: # Rだと見つかった場所の→へ行く
        mark = RL[idx]

    if (i - mark) % 2 == 0: # Rの位置から偶数離れていればRの方
        ans[mark] += 1
    else: # 奇数離れていればLの位置へ行く
        ans[mark + 1] += 1

print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
ans = [1] * len(S)
N = len(S)
prev = ans
prev_prev = None
counter = 0
while True:
    new_ans = [0] * len(ans)
    for i in range(N):
        if i == 0:
            new_ans[i] = ans[i + 1] if S[i + 1] == 'L' else 0
        elif i == N - 1:
            new_ans[i] = ans[i - 1] if S[i - 1] == 'R' else 0
        else:
            lv = ans[i - 1] if S[i - 1] == 'R' else 0
            rv = ans[i + 1] if S[i + 1] == 'L' else 0
            new_ans[i] = lv + rv
    # print(new_ans)

    if prev_prev is None:
        prev_prev = ans
        prev = new_ans
        ans = new_ans
    else:
        prev_prev = prev
        prev = ans
        ans = new_ans

    if prev_prev == ans:
        break
    ans = new_ans
    counter += 1

if counter % 2 == 0:
    print(*prev)
else:
    print(*ans)


Fixed submission:
# 解説を読んでからrun-length
# TLEだったので見て修正

import bisect

S = input()
RL = []
for i in range(len(S) - 1):
    if S[i] == 'R' and S[i + 1] == 'L':
        RL.append(i)


ans = [0] * len(S)
for i in range(len(S)):
    idx = bisect.bisect_left(RL, i)
    if S[i] == 'L':  # Lだと見つかった場所の←へ行く
        mark = RL[idx - 1]
    else: # Rだと見つかった場所の→へ行く
        mark = RL[idx]

    if (i - mark) % 2 == 0: # Rの位置から偶数離れていればRの方
        ans[mark] += 1
    else: # 奇数離れていればLの位置へ行く
        ans[mark + 1] += 1

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/agc036/tasks/agc036_a

S = int(input())

def divisors(N):
    ans = []
    i = 1
    while i * i <= N:
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
        i += 1
    ans.sort()
    return ans

if S <= 10 ** 9:
    print(0, 0, S, 0, 0, 1)
else:
    i = 1
    N = S
    while i * i <= N and i <= 10 ** 9:
        if N % i == 0:
            if N // i <= 10 ** 9:
                print(0, 0, N // i, 0, 0, i)
                exit()
            if N // i != i:
                if N // i <= 10 ** 9:
                    print(0, 0, N // i, 0, 0, i)
                    exit()
        i += 1


Fixed submission:
# https://atcoder.jp/contests/agc036/tasks/agc036_a

S = int(input())
x1 = 0
y1 = 0
x2 = 1000000000
y2 = 1
v = 1000000000
x = (v - S % v) % v
y = (S + x) // v

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x, y))
Buggy python submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())
S = input()
S = "#" + S + "#"

# A -= 1
# B -= 1
# C -= 1
# D -= 1

def can_reach(start, end):
    for i in range(start, end + 2):
        if S[i] == '#' and S[i + 1] == '#':
            return False
    return True


if not can_reach(A, C) or not can_reach(B, D):
    print("No")
    exit()

if C > D:
    cover = False
    for i in range(B, D + 1):
        if S[i - 1] == '.' and S[i] == '.' and S[i + 1] == '.':
            cover = True
    if not cover:
        print("No")
        exit()


print("Yes")

Fixed submission:
N, A, B, C, D = map(int, input().split())
S = input()
S = "#" + S + "#"

# A -= 1
# B -= 1
# C -= 1
# D -= 1

def can_reach(start, end):
    for i in range(start, end + 1):
        if S[i] == '#' and S[i + 1] == '#':
            return False
    return True


if not can_reach(A, C) or not can_reach(B, D):
    print("No")
    exit()

if C > D:
    cover = False
    for i in range(B, D + 1):
        if S[i - 1] == '.' and S[i] == '.' and S[i + 1] == '.':
            cover = True
    if not cover:
        print("No")
        exit()


print("Yes")

Buggy python submission (verdict: Runtime Error):
N, A, B, C, D = map(int, input().split())
S = input()
S = "#" + S + "#"

# A -= 1
# B -= 1
# C -= 1
# D -= 1

def can_reach(start, end):
    for i in range(start, end + 2):
        if S[i] == '#' and S[i + 1] == '#':
            return False
    return True


if not can_reach(A, C) or not can_reach(B, D):
    print("No")
    exit()

if C > D:
    cover = False
    for i in range(B, D + 1):
        if S[i - 1] == '.' and S[i] == '.' and S[i + 1] == '.':
            cover = True
    if not cover:
        print("No")
        exit()


print("Yes")

Fixed submission:
N, A, B, C, D = map(int, input().split())
S = input()
S = "#" + S + "#"

# A -= 1
# B -= 1
# C -= 1
# D -= 1

def can_reach(start, end):
    for i in range(start, end + 1):
        if S[i] == '#' and S[i + 1] == '#':
            return False
    return True


if not can_reach(A, C) or not can_reach(B, D):
    print("No")
    exit()

if C > D:
    cover = False
    for i in range(B, D + 1):
        if S[i - 1] == '.' and S[i] == '.' and S[i + 1] == '.':
            cover = True
    if not cover:
        print("No")
        exit()


print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
# 解説
# ABC -> CBA
# BCは増えない&離れない
# AD -> DAを考える

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

S = input()
S = S.replace("BC", "D")
# print(S)

# ADからなる連続領域に分ける
ranges = []
i = 0
while i < len(S):
    while i < len(S) and S[i] != 'A' and S[i] != 'D':
        i += 1
    j = i
    while j < len(S) and (S[j] == 'A' or S[j] == 'D'):
        j += 1
    ranges.append((i, j - 1))
    i = j + 1

# 各AD列の点灯数を求める
total = 0
for (i, j) in ranges:
    # print(i, j, S[i:j+1])
    ans = 0
    for i in range(i, j + 1):
        for j in range(i + 1, j + 1):
            if S[i] == 'A' and S[j] == 'D':
                ans += 1
            # print(i, j, S[i], S[j])
    total += ans
print(total)



Fixed submission:
# 解説
# ABC -> CBA
# BCは増えない&離れない
# AD -> DAを考える
# Aの右にBCが何個あるか

s = input()
n = len(s)
i = 0
ans = 0
count_a = 0

while i < n:
    if s[i] == 'A':
        count_a += 1
    elif i < n - 1 and s[i:i+2] == 'BC' and count_a > 0:
        ans += count_a
        i += 1
    else:
        count_a = 0
    i += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/agc034/tasks/agc034_b

S = input()
count = 0
while "ABC" in S:
    # print(S)
    count += S.count("ABC")
    S = S.replace("ABC", "BCA")
print(count)

Fixed submission:
# 解説
# ABC -> CBA
# BCは増えない&離れない
# AD -> DAを考える
# Aの右にBCが何個あるか

s = input()
n = len(s)
i = 0
ans = 0
count_a = 0

while i < n:
    if s[i] == 'A':
        count_a += 1
    elif i < n - 1 and s[i:i+2] == 'BC' and count_a > 0:
        ans += count_a
        i += 1
    else:
        count_a = 0
    i += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

from math import ceil, floor

def divisors(N):
    ans = []
    i = 1
    while i * i <= N:
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
        i += 1
    ans.sort()
    return ans

N = int(input())
# N = 1000000
fN = divisors(N)
total = 0
for i in range(len(fN) - 1):
    if fN[i + 1] - fN[i] == 1:
        continue
    mp = N // fN[i]
    mpp = N // fN[i + 1]
    # print(fN[i], fN[i + 1], " | [{},{}]".format(mpp, mp))
    for mm in range(mpp, mp):
        for rr in range(1, fN[i] + 1):
            # print(N - rr, floor((N - rr) / mm) == ceil((N - rr) / mm) and rr == mm)
            if floor((N - rr) / mm) == ceil((N - rr) / mm) and rr == mm:
                # print(rr, mm)
                total += (N - rr) // mm
            # print(mm, rr, floor((N - rr) / mm))
print(total)
    
# print()
# total2 = 0
# for m in range(1, N + 1):
#     f1 = floor(N / m)
#     f2 = N % m
#     if f1 == f2:
#         print(m, f1, f2, f1 == f2)
#         total2 += m
# print(total2)

Fixed submission:
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

from math import ceil, floor

def divisors(N):
    ans = []
    i = 1
    while i * i <= N:
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
        i += 1
    ans.sort()
    return ans

N = int(input())
fN = divisors(N)

total = 0
for m in fN[1:]:
    m -= 1
    if floor(N / m) == N % m:
        total += m
print(total)
Buggy python submission (verdict: Runtime Error):
a, b, c == map(int, input().split())
if a == b and b == c:
  print("Yes")
else:
  print("No")

Fixed submission:
a, b, c = map(int, input().split())
if a == b and b == c:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

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

# 最後は全部つながってない
# うしろから順番につなぐ
edges = []
for _ in range(M):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    edges.append((ai, bi))
edges.reverse()

ans = [N * (N - 1) // 2]
for (ai, bi) in edges:
    u1 = uf.group_count()
    if not uf.same(ai, bi):
        ans.append(ans[-1] - uf.size(ai) * uf.size(bi))
    else:
        ans.append(ans[-1])
    uf.unite(ai, bi)

for a in ans[::-1][1:]:
    print(a)

Fixed submission:
# https://atcoder.jp/contests/abc120/tasks/abc120_d

######### Union Find ########
class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def count(self, x):
        return -self.root[self.find(x)]


if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = []
    for _ in range(m):
        ai, bi = map(int, input().split())
        ab.append((ai - 1, bi - 1))
    all_n = n * (n - 1) // 2
    ans = [all_n]
    uf = UnionFind(n)

    # 後ろから
    for i in range(m - 1):
        ai, bi = ab[-1 - i]
        # print(ai, bi)

        if not uf.is_same(ai, bi):
            all_n -= uf.count(ai) * uf.count(bi)
        uf.unite(ai, bi)
        ans.append(all_n)

    for v in ans[::-1]:
        print(v)
Buggy python submission (verdict: Runtime Error):
from math import floor
n = int(input())
a = int(input())
b = int(input())

print(ceil(n / a) * ceil(n / b))

Fixed submission:
from math import ceil
n = int(input())
a = int(input())
b = int(input())
print((n - a + 1) * (n - b + 1))
Buggy python submission (verdict: Runtime Error):
#
# N M
# S
# T
#
# find X (length L, LはN, Mで割り切れる (最小公倍数))
#
# e.g.
# 3 2
# acp
# ae
#
# X
# - 
# - 1, L/N+1, 2L/N+1, ... はSになる
# - 1, L/M+1, 2L/M+1, ... はTになる

from fractions import gcd

N, M = map(int, input().split())
S = input()
T = input()
L = N * M // gcd(N, M)

if S[0] != T[0]:
    print(-1)
    exit()

# 仮の文字列 (中身は何でもいい)
ans = [S[0]] + ["-"] * (L - 1)

# Sを置く
for i in range(N):
    ans[i * L // N] = S[i]

# print(ans)

# Tを置く
# 既にSが入っている場合，Tと整合するか確認する
for i in range(M):
    index = i * L // M
    if ans[index] != "-":
        if ans[index] != T[i]:
            print(-1)
            exit()
        else:
            ans[index] = T[i]
    else:
        ans[index] = T[i]


print(L)

Fixed submission:
from fractions import gcd

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

lcm = N * M // gcd(N, M)
n = N // gcd(N, M)
m = M // gcd(N, M)

for k in range(gcd(N, M)):
    a = k * n
    b = k * m
    if S[a] != T[b]:
        print(-1)
        exit()

print(lcm)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import setrecursionlimit
from fractions import gcd

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

#nを素因数分解したリストを返す
# def prime_decomposition(n):
#     i = 2
#     table = []
#     while i * i <= n:
#         while n % i == 0:
#             n //= i
#             table.append(i)
#         i += 1
#     if n > 1:
#         table.append(n)
#     return table


memo = {}
# n個の数字でmを作る場合のmax
def dfs(n, m):
    if n == 1:
        return m
    elif n >= m:
        return 1
    else:
        if (n, m) in memo:
            return memo[n, m]
        else:
            # print(n, m)
            ans = []
            for first in range(2, m - n + 2):
                # print(first, m - first)
                ans_first = gcd(first, dfs(n - 1, m - first))
                ans.append(ans_first)
                # ans_first = dfs(n - 1, m - first)
            # print(ans)
            # ans.append(gcd(first, dfs(n - 1, m - first)))
            # return 1  # max(ans)
            memo[n, m] = max(ans)
            return memo[n, m]


# print(N, M, prime_decomposition(M))
print(dfs(N, M))

Fixed submission:
# (o) recursionはダメ
# (o) 素因数はO(sqrt(N))で求められる
# (x) 具体的な計算

"""
Memo:
- A=[a1,...,an]の最大公約数をDとする
- sum(A)=MもDで割り切れる，よってDはMの約数 (Mも割れる)

2条件
- DがMの約数であって，M >= N * Dであるとき
    - a1=...=an-1=D, an = M - (N - 1) * D は全てDで割り切れる (最大公約数)
- Mの約数かつM // N以下の整数で最大
"""

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


# 約数を求める
factors = []
i = 1
while i * i <= M + 1:
    if M % i == 0:
        factors.append(i)
        if M // i != i:
            factors.append(M // i)
    i += 1

factors.sort(reverse=True)
# Mの約数でM // N以下の最大
for f in factors:
    if M // f >= N:
        print(f)
        exit()

# ans = 1
# for factor in factors:
#     if factor <= M // N:
#         ans = factor
# print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
ca = [0] * (len(a) + 1)
for i in range(n):
    ca[i + 1] = ca[i] + a[i]

ans = 0
for i in range(n):
    # print(a[i], ca[i], ca, ca[i + 1:], ca[i + 1:].count(ca[i]))
    ans += ca[i + 1:].count(ca[i])
print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ca = [0] * (len(a) + 1)
for i in range(n):
    ca[i + 1] = ca[i] + a[i]


# TLE
# ans = 0
# for i in range(n):
#     # print(a[i], ca[i], ca, ca[i + 1:], ca[i + 1:].count(ca[i]))
#     ans += ca[i + 1:].count(ca[i])
# print(ans)

from collections import Counter

ans = 0
cac = Counter(ca)
# print(cac)
# ca.sort()
for v, c in cac.items():
    if c >= 2:
        ans += c * (c - 1) // 2
print(ans)
Buggy python submission (verdict: Runtime Error):
-*- coding: utf-8 -*-
N = input()

if len(N) == 1:
  # 1桁の数字
  print(N)
elif all(map(lambda x: x == '9', N[1:])):
  # 下位が全部9の場合
  print(sum(int(n) for n in N))
else:
  # 下位を全部9にする例
    print(9 * (len(N) - 1) + int(N[0]) - 1)
 

Fixed submission:
N = input()
if len(N) == 1:
  # 1桁の数字
  print(N)
elif all(map(lambda x: x == '9', N[1:])):
  # 下位が全部9の場合
  print(sum(int(n) for n in N))
else:
  # 下位を全部9にする例
    print(9 * (len(N) - 1) + int(N[0]) - 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

print(0, flush=True)
begin = input()

l, r = 0, N
while abs(r - l) > 1:
    mid = (l+r) // 2
    print(mid, flush=True)
    sol = input()
    if sol == "Vacant":
        l = mid
        break
    elif sol % 2 == 0:
        if sol != begin:
            r = mid
        else:
            l = mid
    else:
        if sol != begin:
            l = mid
        else:
            r = mid

print(l)


Fixed submission:
N = int(input())

print(0, flush=True)
begin = input()

l, r = 0, N
while abs(r - l) > 1:
    mid = (l+r) // 2
    print(mid, flush=True)
    sol = input()
    if sol == "Vacant":
        l = mid
        break
    elif mid % 2 == 0:
        if sol != begin:
            r = mid
        else:
            l = mid
    else:
        if sol != begin:
            l = mid
        else:
            r = mid

print(l)