Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
h, n = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(n)]
h_max = 10 ** 4
inf = 10 ** 9
dp = [inf] * (h_max + 1)
dp[0] = 0
for h_target in range(1, h_max + 1):
    for attack, mp in AB:
        h_remain = max(0, h_target - attack)
        dp[h_target] = min(dp[h_target], dp[h_remain] + mp)
print(dp[h])


Fixed submission:
h, n = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(n)]
h_max = 10 ** 4
inf = 10 ** 9
dp = [inf] * (h_max + 1)
dp[0] = 0
for h_target in range(1, h_max + 1):
    for attack, mp in AB:
        h_remain = max(0, h_target - attack)
        dp[h_target] = min(dp[h_target], dp[h_remain] + mp)
print(dp[h])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import namedtuple
from queue import Queue
from copy import deepcopy

def bfs(start, stage):
    if stage[start.y][start.x] == "#":
        return -1
    ans = 0
    q = Queue()
    q.put(start)
    stage[start.y][start.x] = 0
    while not q.empty():
        current = q.get()
        for move in moves:
            nxt = point(current.y + move.y, current.x + move.x)
            can_move = 0 <= nxt.y < h and 0 <= nxt.x < w and stage[nxt.y][nxt.x] == "."
            if can_move:
                q.put(nxt)
                stage[nxt.y][nxt.x] = stage[current.y][current.x] + 1
                ans = stage[current.y][current.x] + 1
    return ans


point = namedtuple("point", "y, x")
moves = [point(-1, 0), point(0, 1), point(1, 0), point(0, -1)]
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
ans = -1
for y in range(h):
    for x in range(w):
        steps = bfs(point(y, x), deepcopy(S))
        ans = max(ans, steps)
print(ans)


Fixed submission:
from collections import namedtuple
from queue import Queue
from copy import deepcopy

def bfs(start, stage):
    if stage[start.y][start.x] == "#":
        return -1
    ans = 0
    q = Queue()
    q.put(start)
    stage[start.y][start.x] = 0
    while not q.empty():
        current = q.get()
        for move in moves:
            nxt = point(current.y + move.y, current.x + move.x)
            can_move = 0 <= nxt.y < h and 0 <= nxt.x < w and stage[nxt.y][nxt.x] == "."
            if can_move:
                q.put(nxt)
                stage[nxt.y][nxt.x] = stage[current.y][current.x] + 1
                ans = stage[current.y][current.x] + 1
    return ans


point = namedtuple("point", "y, x")
moves = [point(-1, 0), point(0, 1), point(1, 0), point(0, -1)]
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
ans = -1
for y in range(h):
    for x in range(w):
        steps = bfs(point(y, x), deepcopy(S))
        ans = max(ans, steps)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = ""
for x in range(N):
    ans += " " + str(A.index(x+1) + 1)
print(ans.lstrip(" "))

Fixed submission:
N = int(input())
A = map(int,input().split())
d = {}
for i, a in enumerate(A):
    d[a] = i + 1
ans = ""
for i in range(N):
    ans += " " + str(d[i+1])
print(ans.lstrip(" "))
Buggy python submission (verdict: Time Limit Exceeded):
print(sum(range(1, int(input()))))


Fixed submission:
N = int(input())
print((1 + (N - 1)) * (N - 1) // 2)
Buggy python submission (verdict: Time Limit Exceeded):
l, r = map(int, input().split())
ans = 2020
for i in range(l, r):
    for j in range(i+1, r+1):
        tmp = i * j % 2019
        ans = tmp if tmp < ans else ans
        if ans == 0:
            break

print(ans)


Fixed submission:
l, r = map(int, input().split())
ans = 2020
if l <= (l // 2019 + 1) * 2019 <= r:
    ans = 0
else:
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            tmp = i * j % 2019
            ans = tmp if tmp < ans else ans
            if ans == 0:
                break
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import inf

l, r = map(int, input().split())
ans = inf
for i in range(l, r):
    for j in range(i+1, r+1):
        tmp = i * j % 2019
        ans = tmp if tmp < ans else ans
        if ans == 0:
            break

print(ans)


Fixed submission:
l, r = map(int, input().split())
ans = 2020
if l <= (l // 2019 + 1) * 2019 <= r:
    ans = 0
else:
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            tmp = i * j % 2019
            ans = tmp if tmp < ans else ans
            if ans == 0:
                break
print(ans)
Buggy python submission (verdict: Runtime Error):
def make_guide():
    num: int = int(input())
    lst = [(i + 1, *input().split()) for i in range(num)]
    lst = sorted(sorted(lst, key=lambda t: t[2]), key=lambda t: t[1])
    return lst


def test_display():
    lst = make_guide()
    for i, lst in lst:
        print(str(i) + " " + lst[0] + " " + lst[1])


def display():
    lst = make_guide()
    for i, city, point in lst:
        print(i)


if __name__ == "__main__":
    display()

Fixed submission:
def make_guide():
    num = int(input())
    lst = [(i + 1, input().split()) for i in range(num)]
    # TODO fix
    # 同じものが存在したら、っていう条件のもとでないとダメ
    # あと数字は降順
    lst = sorted(lst, key=lambda t: int(t[1][1]), reverse=True)
    lst = sorted(lst, key=lambda t: t[1][0])
    return lst


def test_display():
    lst = make_guide()
    for i, guides in lst:
        print(str(i) + " " + guides[0] + " " + guides[1])


def display():
    lst = make_guide()
    for i, guides in lst:
        print(i)


if __name__ == "__main__":
    display()

Buggy python submission (verdict: Runtime Error):
def make_guide():
    num: int = int(input())
    lst = [(i, input().split()) for i in range(num)]
    print(lst[0])
    lst = sorted(sorted(lst, key=lambda t: t[1][1]), key=lambda t: t[1][0])
    return lst
 
if __name__ == "__main__":
    display()

Fixed submission:
def make_guide():
    num = int(input())
    lst = [(i + 1, input().split()) for i in range(num)]
    # TODO fix
    # 同じものが存在したら、っていう条件のもとでないとダメ
    # あと数字は降順
    lst = sorted(lst, key=lambda t: int(t[1][1]), reverse=True)
    lst = sorted(lst, key=lambda t: t[1][0])
    return lst


def test_display():
    lst = make_guide()
    for i, guides in lst:
        print(str(i) + " " + guides[0] + " " + guides[1])


def display():
    lst = make_guide()
    for i, guides in lst:
        print(i)


if __name__ == "__main__":
    display()
Buggy python submission (verdict: Runtime Error):
n, g = map(int, input().split())
cards = [[int(x) for x in input().split()] for _ in range(g)]

cards.sort(key=lambda x: x[0])
lmx = cards[g - 1][0]
cards.sort(key=lambda x: x[1])
rmn = min(cards[0][1], n)

print(max(0, rmn - lmx + 1))


Fixed submission:
A, B = [int(x) for x in input().split()]
if A <= 5:
    print(0)
elif A <= 12:
    print(int(B / 2))
else:
    print(B)
Buggy python submission (verdict: Runtime Error):
N = int(input())
lim = int(N ** 0.5) + 1
ans = 0
for i in range(1, lim + 1):
    m = N // i
    quotient = N // m
    while m != 0:
        remainder = N % m
        if N // m != quotient or remainder > i:
            break
        if quotient == remainder:
            ans += m
            break
        m -= 1
print(ans)


Fixed submission:
N = int(input())
lim = int(N ** 0.5)
ans = 0
for i in range(1, lim + 1):
    m = N // i
    quotient = N // m
    while m != 0:
        remainder = N % m
        if N // m != quotient or remainder > i:
            break
        if quotient == remainder:
            ans += m
            break
        m -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()

cc = []

for idx in range(N):
    if S[idx:idx + 2] == "AC":
        cc.append(1)
    else:
        cc.append(0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(sum(cc[l - 1:r]) - cc[r - 1])


Fixed submission:
N, Q = map(int, input().split())
S = input()

cc = []

acc = 0

for idx in range(N):
    if S[idx - 1:idx + 1] == "AC":
        acc = acc + 1
    cc.append(acc)

for i in range(Q):
    l, r = map(int, input().split())
    print(cc[r - 1] - cc[l - 1])

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

cc = []

for idx in range(len(S) - 1):
    if S[idx:idx + 2] == "AC":
        cc.append(1)
    else:
        cc.append(0)

for _ in range(Q):
    l, r = map(int, input().split())
    print(sum(cc[l - 1:r]) - cc[r - 1])


Fixed submission:
N, Q = map(int, input().split())
S = input()

cc = []

acc = 0

for idx in range(N):
    if S[idx - 1:idx + 1] == "AC":
        acc = acc + 1
    cc.append(acc)

for i in range(Q):
    l, r = map(int, input().split())
    print(cc[r - 1] - cc[l - 1])

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

N, Q = map(int, sys.stdin.readline().split())
S = sys.stdin.readline().strip()
for _ in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(len(S[l - 1:r].split("AC")) - 1)


Fixed submission:
N, Q = map(int, input().split())
S = input()

cc = []

acc = 0

for idx in range(N):
    if S[idx - 1:idx + 1] == "AC":
        acc = acc + 1
    cc.append(acc)

for i in range(Q):
    l, r = map(int, input().split())
    print(cc[r - 1] - cc[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
def solve(remains, nums):
    if (len(remains)) == 0:
        [print(num) for num in nums[::-1]]
        exit()
    n_remains = []
    n_nums = []
    for i, num in enumerate(remains):
        if i + 1 == num:
            n_remains.append(remains[:i] + remains[i + 1:])
            n_nums.append(nums + [i + 1])
    if len(n_remains) == 0:
        return False
    for n_remain, n_num in zip(n_remains, n_nums):
        solve(n_remain, n_num)


n = int(input())
B = [int(x) for x in input().split()]

solve(B, [])
print(-1)


Fixed submission:
def solve(remains, nums):
    if (len(remains)) == 0:
        [print(num) for num in nums[::-1]]
        exit()
    n_remain = None
    n_num = None
    for i, num in enumerate(remains):
        if i + 1 == num:
            n_remain = remains[:i] + remains[i + 1:]
            n_num = nums + [i + 1]
    if n_remain is None:
        return False
    solve(n_remain, n_num)


n = int(input())
B = [int(x) for x in input().split()]

solve(B, [])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
def solve(remains, nums):
    if (len(remains)) == 0:
        [print(num) for num in nums[::-1]]
        exit()
    n_remains = []
    n_nums = []
    for i, num in enumerate(remains):
        if i + 1 == num:
            n_remains.append(remains[:i] + remains[i + 1:])
            n_nums.append(nums + [i + 1])
    if len(n_remains) == 0:
        return False
    for n_remain, n_num in zip(n_remains, n_nums):
        solve(n_remain, n_num)


n = int(input())
B = [int(x) for x in input().split()]

solve(B, [])
print(-1)


Fixed submission:
def solve(remains, nums):
    if (len(remains)) == 0:
        [print(num) for num in nums[::-1]]
        exit()
    n_remain = None
    n_num = None
    for i, num in enumerate(remains):
        if i + 1 == num:
            n_remain = remains[:i] + remains[i + 1:]
            n_num = nums + [i + 1]
    if n_remain is None:
        return False
    solve(n_remain, n_num)


n = int(input())
B = [int(x) for x in input().split()]

solve(B, [])
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
import re

S = input()

trimmed = 0

while True:
    tmp = re.split("01|10", S)
    if len(tmp) == 1:
        break
    else:
        trimmed = trimmed + len(tmp) - 1
        S = "".join(tmp)

print(trimmed * 2)


Fixed submission:
S = input()

zero = 0
one = 0

for ch in S:
    if ch == "0":
        zero = zero + 1
    else:
        one = one + 1

print(min(zero, one) * 2)
Buggy python submission (verdict: Runtime Error):
from datetime import date
dt = date.fromisoformat(input().replace('/', '-'))
th = date.fromisoformat('2019-04-30')
if dt <= th:
    print('Heisei')
else:
    print('TBD')


Fixed submission:
y, m, d = map(int, input().split('/'))
if y < 2019:
    print('Heisei')
elif y == 2019 and m < 5:
    print('Heisei')
else:
    print('TBD')
Buggy python submission (verdict: Time Limit Exceeded):
N = input()
A = {int(x) for x in input().split()}

while True:
    if len(A) == 1:
        break
    mn = min(A)
    A = {x for x in A if x % mn != 0 or x == mn}

print(A.pop())

Fixed submission:
N = input()
A = {int(x) for x in input().split()}

while True:
    if len(A) == 1:
        break
    tmp = list(A)
    mn = min(tmp)
    for idx in range(len(tmp)):
        if tmp[idx] != mn:
            tmp[idx] = tmp[idx] % mn if tmp[idx] % mn != 0 else mn
    A = set(tmp)

print(A.pop())
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if a > b:
        a, b = b, a
    if b % a == 0:
        return a
    a, b = b / a, a


def reduce(f, l):
    if len(l) == 1:
        return l[0]
    c = l[0]
    for i in l[1:]:
        c = f(c, i)
    return c


X = int(input().split()[1])
x = [abs(int(x) - X) for x in input().split()]

print(reduce(gcd, x))


Fixed submission:
from functools import reduce
from fractions import gcd

X = int(input().split()[1])
x = [abs(int(x) - X) for x in input().split()]

print(reduce(gcd, x))

Buggy python submission (verdict: Runtime Error):
from functools import reduce
from math import gcd

X = int(input().split()[1])
x = [abs(int(x) - X) for x in input().split()]

print(reduce(gcd, x))


Fixed submission:
from functools import reduce
from fractions import gcd

X = int(input().split()[1])
x = [abs(int(x) - X) for x in input().split()]

print(reduce(gcd, x))

Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt, floor
from functools import reduce


def divisors(a):
    return {i for i in range(1, floor(sqrt(a)) + 1) if a % i == 0}\
        .union({a // i for i in range(1, floor(sqrt(a)) + 1) if a % i == 0})


def greatest_common_divisor(a, b):
    return max(divisors(a).intersection(divisors(b)))


def greatest_common_divisor_of(lst):
    return reduce(greatest_common_divisor, lst)


X = int(input().split()[1])
xi = list(map(int, input().split()))
x = [abs(x - X) for x in xi]
print(greatest_common_divisor_of(x))


Fixed submission:
from functools import reduce
from fractions import gcd

X = int(input().split()[1])
x = [abs(int(x) - X) for x in input().split()]

print(reduce(gcd, x))

Buggy python submission (verdict: Runtime Error):
from math import sqrt, floor
from functools import reduce


def divisors(a):
    return {i for i in range(1, floor(sqrt(a)) + 1) if a % i == 0}\
        .union({a // i for i in range(1, floor(sqrt(a)) + 1) if a % i == 0})


def greatest_common_divisor(a, b):
    return max(divisors(a).intersection(divisors(b)))


def greatest_common_divisor_of(lst):
    return reduce(greatest_common_divisor, lst)


X = int(input().split()[1])
xi = list(map(int, input().split()))
x = [x - X for x in xi]
print(greatest_common_divisor_of(x))

Fixed submission:
from functools import reduce
from fractions import gcd

X = int(input().split()[1])
x = [abs(int(x) - X) for x in input().split()]

print(reduce(gcd, x))
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_right
from math import ceil

n, h = map(int, input().split())
A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
B_sorted = sorted(B)
B_cumulative_sum = list(B_sorted)
for i in range(n - 2, -1, -1):
    B_cumulative_sum[i] += B_cumulative_sum[i + 1]
    if B_cumulative_sum[i] > h:
        print(n - i)
        exit()
cnt = int(1e9)
for a, b in zip(A, B):
    target_idx = bisect_right(B_sorted, a)
    throws = n - target_idx
    hp_remains_after_throw = h - B_cumulative_sum[target_idx]
    attacks = ceil(hp_remains_after_throw / a)
    cnd = throws + attacks
    cnt = min(cnt, cnd)
print(cnt)


Fixed submission:
from math import ceil

n, hp = map(int, input().split())
A = []
B = []
for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
MAX_A = max(A)
B.sort(reverse=True)

cnt = 0
for b in B:
    if b > MAX_A:
        hp -= b
        cnt += 1
    else:
        break
    if hp <= 0:
        break
if hp > 0:
    cnt += ceil(hp / MAX_A)
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right

N = int(input())
A = sorted([int(x) for x in input().split()])
B = sorted([int(x) for x in input().split()])
C = sorted([int(x) for x in input().split()])

ans = 0
for b in B:
    ans += len(A[:bisect_right(A, b - 1)]) * len(C[bisect_left(C, b + 1):])
print(ans)


Fixed submission:
from bisect import bisect_left, bisect_right

N = int(input())
A = sorted([int(x) for x in input().split()])
B = sorted([int(x) for x in input().split()])
C = sorted([int(x) for x in input().split()])

ans = 0
for b in B:
    ans += bisect_right(A, b - 1) * (N - bisect_left(C, b + 1))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
# dict = defaultdict(bool)  # int/bool/list....
# dict[r] = True
orgr = r
d = 1
while r > 0:
    d += 1
    r = (10 * r + 7) % K
    # if dict[r]:
    if r == orgr:
        print(-1)
        sys.exit()

print(d)

Fixed submission:
import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
orgr = r
d = 1
for _ in range(K + 1):
    if r == 0:
        print(d)
        break
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()
    dict[r] = True

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
d = 1
while r > 0:
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()

print(d)


Fixed submission:
import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
orgr = r
d = 1
for _ in range(K + 1):
    if r == 0:
        print(d)
        break
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()
    dict[r] = True

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
d = 1
while r > 0:
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()

print(d)


Fixed submission:
import sys
from collections import defaultdict
K = int(input())
n = len(str(K))

r = 7 % K
dict = defaultdict(bool)  # int/bool/list....
dict[r] = True
orgr = r
d = 1
for _ in range(K + 1):
    if r == 0:
        print(d)
        break
    d += 1
    r = (10 * r + 7) % K
    if dict[r]:
        print(-1)
        sys.exit()
    dict[r] = True
Buggy python submission (verdict: Runtime Error):
def ceil(n, m):
    return -(-n // m)

# K回のカットで長さlにできるかどうか
def possible(l, K):
    cut = 0
    for i in range(N):
        cut += ceil(A[i], l) - 1
        if cut > K:
            return False
    return True

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
L = sum(A)

ng = (L // (N + K)) - 1  # min -1
ok = max(A)

while ok - ng > 1:
    mid = (ok + ng) // 2
    if possible(mid, K):
        ok = mid
    else:
        ng = mid

print(ok)

Fixed submission:
def ceil(n, m):
    return -(-n // m)

# K回のカットで長さlにできるかどうか
def possible(l, K):
    cut = 0
    if l <= 0:
        return False
    for i in range(N):
        cut += ceil(A[i], l) - 1
        if cut > K:
            return False
    return True

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
L = sum(A)

ng = (L // (N + K)) - 1  # min -1
ok = max(A)

while ok - ng > 1:
    mid = (ok + ng) // 2
    if possible(mid, K):
        ok = mid
    else:
        ng = mid

print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
f = [0] + [1] + [2] * (N - 1)
for d in range(2, int(N ** 0.5) + 1):
    for i in range((N // d) * d, d * d - 1, -d):
        if d * d == i:
            f[i] += 1
        else:
            f[i] += 2

ans = 0
for i in range(1, N + 1):
    ans += i * f[i]

print(ans)

Fixed submission:
N = int(input())
ans = 0
for d in range(1, N + 1):
    ans += (1 + N // d) * (N // d) * d // 2

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

N = int(input())
A = [int(x) for x in input().split()]
A.sort()
B = [True] * N
for i in range(N):
    if not B[i]: continue
    jr = bisect.bisect_right(A, A[i])
    if jr > i + 1:
        for jj in range(i, jr):
            B[jj] = False

    for a in range(2 * A[i], A[-1] + 1, A[i]):
        jl = bisect.bisect_left(A, a)
        jr = bisect.bisect_right(A, a)
        if A[jl] == a:
            for jj in range(jl, jr):
                B[jj] = False
print(B.count(True))

Fixed submission:
from collections import Counter, defaultdict

N = int(input())
A = [int(x) for x in input().split()]
A.sort()

C = Counter(A)
D = defaultdict(bool)
for key in C.keys():
    D[key] = True

B = [True] * N
ans = 0
for i in range(N):
    if not D[A[i]]: continue
    if C[A[i]] > 1:
        D[A[i]] = False

    for a in range(2 * A[i], A[-1] + 1, A[i]):
        D[a] = False

ans = 0
for key in D:
    if D[key]:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = len(S)
k = 2019

# Let S = s[0]s[1]....s[n - 1] and
# let A[i] = s[i]s[i+1]...s[n-1] = s[i]*10^(n-i-1) + ... + s[n-1]*10^0
A = [0] * (n + 1) # A[n]はダミー

w = 1
for i in range(n - 1, -1, -1):
    A[i] = (A[i + 1] + w * int(S[i])) % k
    w = w * 10 % k

ans = 0
for j in range(k):
    c = A.count(j)
    ans += c * (c - 1) // 2

print(ans)

Fixed submission:
S = input()
n = len(S)
k = 2019

# Let S = s[0]s[1]....s[n - 1] and
# let A[i] = s[i]s[i+1]...s[n-1] = s[i]*10^(n-i-1) + ... + s[n-1]*10^0
A = [0] * (n + 1) # A[n] = 0
d = {0:1}

w = 1
for i in range(n - 1, -1, -1):
    A[i] = (A[i + 1] + w * int(S[i])) % k
    w = w * 10 % k
    if A[i] in d:
        d[A[i]] += 1
    else:
        d[A[i]] = 1

ans = 0
for j in d:
    ans += d[j] * (d[j] - 1) // 2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

cum_r = [0] * (N + 1)  # cum_r[i] = i文字目までに含まれるRの数（i = 0, .., N)
cum_g = [0] * (N + 1)
cum_b = [0] * (N + 1)

for i in range(1, N + 1):
    cum_r[i] = cum_r[i - 1] + int(S[i - 1] == 'R')
    cum_g[i] = cum_g[i - 1] + int(S[i - 1] == 'G')
    cum_b[i] = cum_b[i - 1] + int(S[i - 1] == 'B')


dp = [0] * (N + 1)
for i in range(3, N + 1):
    dp[i] = dp[i - 1]
    for j in range(1, i - 1):
        if S[i - 1 - j] == S[i - 1]: continue

        if S[i - 1] == 'R':
            if S[i - 1 - j] == 'G':
                dp[i] += cum_b[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'B':
                    dp[i] -= 1
            else: # B
                dp[i] += cum_g[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'G':
                    dp[i] -= 1

        elif S[i - 1] == 'G':
            if S[i - 1 - j] == 'R':
                dp[i] += cum_b[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'B':
                    dp[i] -= 1
            else: # B
                dp[i] += cum_r[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'R':
                    dp[i] -= 1
        else:  # B
            if S[i - 1 - j] == 'R':
                dp[i] += cum_g[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'G':
                    dp[i] -= 1
            else: # G
                dp[i] += cum_r[i - 1 - j]
                if i - 1 - 2 * j >= 0 and S[i - 1 - 2 * j] == 'R':
                    dp[i] -= 1
print(dp[N])


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

sub = 0
for j in range(1, (N - 1) // 2 + 1):
    for i in range(0, N - 2 * j):
        if S[i] != S[i + j] and S[i + j] != S[i + 2 * j] and S[i + 2 * j] != S[i]:
            sub += 1

r = S.count('R')
g = S.count('G')
b = N - r - g

ans = r * g * b - sub
print(ans)