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

Fixed submission:
from collections import deque
from bisect import bisect_left, bisect_right

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

al = list(map(int, input().split()))
bl = list(map(int, input().split()))

al_sums = [0]*(n+1)
bl_sums = [0]*(m)

curr_sum = 0
for i,a in enumerate(al):
    curr_sum += a
    al_sums[i+1] = curr_sum

curr_sum = 0
for i,b in enumerate(bl):
    curr_sum += b
    bl_sums[i] = curr_sum

# print(al_sums)
# print(bl_sums)


ans = 0
for i in range(n+1):
    a_sum = al_sums[i]
    if a_sum > k: continue
    cnt = bisect_right(bl_sums, k-a_sum)
    curr_ans = i+cnt
    # print(i,curr_ans, k-a_sum)
    ans = max(ans,curr_ans)

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left, bisect_right
from itertools import accumulate


n,m,k = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))

al_sums = accumulate(al)
bl_sums = accumulate(bl)

ans = 0
for i in range(0,n+1):
    if i == 0: 
        a_sum = 0
    else:
        a_sum = al_sums[i-1]
    if a_sum > k: 
        continue
    cnt = bisect_right(bl_sums, k-a_sum)
    curr_ans = i+cnt
    ans = max(ans,curr_ans)

print(ans)
Problem p02763 (python)

Fixed submission:
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return


alps = 'abcdefghijklmnopqrstuvwxyz'

n = int(input())
s = list(input())
char_hd_d = {}
for alp in alps:
    char_hd_d[alp] = [0]*(n+1)

for i, si in enumerate(s):
    BIT_update(char_hd_d[si], i+1, 1)

q = int(input())
ansl = []
for _ in range(q):
    command, a, b = input().split()
    if command == '1':
        i = int(a)
        c = b
        i_char = s[i-1]
        BIT_update(char_hd_d[i_char], i, -1)
        BIT_update(char_hd_d[c], i, 1)
        s[i-1] = c 
    else:
        l,r = int(a),int(b)
        cnt = 0
        for alp in alps:
            if BIT_query(char_hd_d[alp], r) - BIT_query(char_hd_d[alp], l-1) > 0:
                cnt += 1
        ansl.append(cnt)

for a in ansl:
    print(a)

Buggy submission (verdict: Runtime Error):
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return


alps = 'abcdefghijklmnopqrstuvwxyz'

n = int(input())
s = input()
char_hd_d = {}
for alp in alps:
    char_hd_d[alp] = [0]*(n+1)

for i, si in enumerate(s):
    BIT_update(char_hd_d[si], i+1, 1)

q = int(input())
ansl = []
for _ in range(q):
    command, a, b = input().split()
    if command == '1':
        i = int(a)
        c = b
        i_char = s[i-1]
        BIT_update(char_hd_d[i_char], i, -1)
        BIT_update(char_hd_d[c], i, 1)
        s[i-1] = c 
    else:
        l,r = int(a),int(b)
        cnt = 0
        for alp in alps:
            if BIT_query(char_hd_d[alp], r) - BIT_query(char_hd_d[alp], l-1) > 0:
                cnt += 1
        ansl.append(cnt)

for a in ansl:
    print(a)
Problem p02771 (python)

Fixed submission:
l = list(map(int,input().split()))
l.sort()
if (l[0]==l[1] and l[1] != l[2]) or (l[0] != l[1] and l[1]==l[2]):
  print('Yes')
else:
  print('No')

Buggy submission (verdict: Runtime Error):
l = list(map(int,input().split()))
l.sort()
if (l[0]==l[1] and l[1]) != l[2] or (l[0] != l[1] and l[1]==l[2]:
  print('Yes')
else:
  print('No')
Problem p02815 (python)

Fixed submission:

n = int(input())
cl = list(map(int, input().split()))
cl.sort(reverse=True)
MOD = 10**9+7

ans = 0
num = pow(2,n-1,MOD)
inc = pow(2,n-2,MOD)
for i in range(n):
    ans += num*cl[i]
    ans%=MOD
    num += inc
    num%=MOD

ans *= pow(2,n,MOD)
ans%=MOD
print(ans)

Buggy submission (verdict: Runtime Error):

n = int(input())
cl = list(map(int, input().split()))
cl.sort(reverse=True)
MOD = 10**9+7

ans = 0
num = pow(2,n-1,MOD)
inc = pow(2,n-2,MOD)
for i in range(n):
    ans += num*cl[i]
    ans%=MOD
    num += inc
    num%=MOD

ans *= pow(2,n,MOD)
ans%=MOD
print(ans)

Buggy submission (verdict: Runtime Error):

n = int(input())
cl = list(map(int, input().split()))
cl.sort(reverse=True)
MOD = 10**9+7

ans = 0
num = pow(2,n-1,MOD)
inc = pow(2,n-2,MOD)
for i in range(n):
    ans += num*cl[i]
    ans%=MOD
    num += inc
    num%=MOD

ans *= pow(2,n,MOD)
ans%=MOD
print(ans)
Problem p02831 (python)

Fixed submission:
import fractions

a, b = map(int, input().split()) 
print(a*b//fractions.gcd(a,b))

Buggy submission (verdict: Runtime Error):
import math

a, b = map(int, input().split()) 
print(a*b/math.gcd(a,b))

Buggy submission (verdict: Runtime Error):
import math
a, b = map(int, input().split()) 
print(a*b//math.gcd(a,b))
Problem p02851 (python)

Fixed submission:
from collections import deque

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

val_cnt = {}
val_cnt[0] = 1
val_q = deque([0])
if k == 1:
    print(0)
    exit()

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    val_cnt.setdefault(val,0)
    ans += val_cnt[val]
    val_cnt[val] += 1
    val_q.append(val)
    if len(val_q) >= k:
        poped = val_q.popleft()
        val_cnt[poped] -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

val_cnt = [0]*k
val_cnt[0] = 1
val_q = deque([0])

ans = 0
curr_sum = 0
for i in range(n):
    curr_sum += al[i]
    curr_sum %= k
    val = (curr_sum - (i+1))%k
    ans += val_cnt[val]
    val_cnt[val] += 1
    val_q.append(val)
    if len(val_q) >= k:
        poped = val_q.popleft()
        val_cnt[poped] -= 1

print(ans)
Problem p02873 (python)

Fixed submission:

import math

def main():
    s = str(input())
    first = s[0]
    cnt_l = []
    tmp_cnt = 1
    prev_s = first
    for curr_s in s[1:]:
        if prev_s != curr_s:
            cnt_l.append(tmp_cnt)
            tmp_cnt = 1
        else:
            tmp_cnt+=1
        prev_s = curr_s
    cnt_l.append(tmp_cnt)

    ans_l = []
    last_num = 0
    if first == '>':
        down_cnt = cnt_l[0]
        for d in range(down_cnt):
            ans_l.append(down_cnt-d)
        cnt_l = cnt_l[1:]

    # if first == '<':
    # print(cnt_l)
    ans_l.append(0)
    last_num = 0
    for i in range(math.ceil(len(cnt_l)/2)):
        # print('i',i)
        up_cnt = cnt_l[i*2]
        if i*2+1 >= len(cnt_l):
            down_cnt = 0
        else:
            down_cnt = cnt_l[i*2+1]
        # print(up_cnt,down_cnt)
        # print()
        for u in range(up_cnt):
            if u != up_cnt-1:
                last_num+=1
                ans_l.append(last_num)
            else:
                last_num = max(last_num+1, down_cnt)
                ans_l.append(last_num)
        for d in range(down_cnt):
            if d==0:
                if last_num > down_cnt:
                    last_num = down_cnt-1
                else:
                    last_num-=1
                ans_l.append(last_num)
            else:
                last_num-=1
                ans_l.append(last_num)

    # print(ans_l)
    print(sum(ans_l))

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):

import math

def main():
    s = str(input())
    first = s[0]
    cnt_l = []
    tmp_cnt = 1
    prev_s = first
    for curr_s in s[1:]:
        if prev_s != curr_s:
            cnt_l.append(tmp_cnt)
            tmp_cnt = 1
        else:
            tmp_cnt+=1
        prev_s = curr_s
    cnt_l.append(tmp_cnt)

    ans_l = []
    last_num = 0
    if first == '>':
        down_cnt = ans_l[0]
        for d in range(down_cnt):
            ans_l.append(down_cnt-1-d)
        ans_l = ans_l[1:]

    # if first == '<':
    # print(cnt_l)
    ans_l.append(0)
    last_num = 0
    for i in range(math.ceil(len(cnt_l)/2)):
        # print('i',i)
        up_cnt = cnt_l[i*2]
        if i*2+1 >= len(cnt_l):
            down_cnt = 0
        else:
            down_cnt = cnt_l[i*2+1]
        # print(up_cnt,down_cnt)
        # print()
        for u in range(up_cnt):
            if u != up_cnt-1:
                last_num+=1
                ans_l.append(last_num)
            else:
                last_num = max(last_num+1, down_cnt)
                ans_l.append(last_num)
        for d in range(down_cnt):
            if d==0:
                if last_num > down_cnt:
                    last_num = down_cnt-1
                else:
                    last_num-=1
                ans_l.append(last_num)
            else:
                last_num-=1
                ans_l.append(last_num)

    # print(ans_l)
    print(sum(ans_l))

if __name__ == "__main__":
    main()
Problem p03426 (python)

Fixed submission:
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d+1, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)

Buggy submission (verdict: Runtime Error):
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)
Problem p03774 (python)

Fixed submission:
n,m = map(int, input().split())
abl = []
cdl = []
for _ in range(n):
    a,b = map(int, input().split())
    abl.append((a,b))

for _ in range(m):
    c,d = map(int, input().split())
    cdl.append((c,d))


for a,b in abl:
    cmin = 10**10
    mini = -1
    for i,(c,d) in enumerate(cdl):
        v = abs(a-c)+abs(b-d)
        if v < cmin:
            cmin = v
            minc,mind = c,d
            mini = i+1
    print(mini)

Buggy submission (verdict: Runtime Error):
n,m = map(int, input().split())
abl = []
cdl = []
for _ in range(n):
    a,b = map(int, input().split())
    abl.append((a,b))

for _ in range(n):
    c,d = map(int, input().split())
    cdl.append((c,d))


for a,b in abl:
    cmin = 10**10
    mini = -1
    for i,(c,d) in enumerate(cdl):
        v = abs(a-c)+abs(b-d)
        if v < cmin:
            cmin = v
            minc,mind = c,d
            mini = i+1
    print(mini)
Problem p02736 (python)

Fixed submission:
def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        # print(' ' * i, *a)
        print(*a)


# test([2, 3, 1, 1, 3, 1, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 2, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 3, 2, 3, 1, 2])
# test([1, 2, 0, 1, 2, 2, 2, 0, 0, 2, 1])
# test([1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0])
# test([0, 0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ])
# test([0] * 21 + [2] + [0] * 21)
# exit()

def solve(n, aaa):
    # シェルピンスキーの三角形
    if '2' not in aaa:
        factor = '3'
        effect = 2
    else:
        factor = '2'
        effect = 1
    # print(factor, effect)

    try_list = []
    m = n - 1
    while m:
        l = 1 << (m.bit_length() - 1)
        m ^= l
        try_list.append((l, m))
    # print(try_list)

    ans = 0
    for i, a in enumerate(aaa):
        if a == factor:
            for l, m in try_list:
                if i >= l:
                    i -= l
                if i == 0:
                    ans ^= effect
                    break
                elif i > m:
                    break
    return ans


n = int(input())
aaa = input()
print(solve(n, aaa))

Buggy submission (verdict: Runtime Error):
from operator import mul


def test(a):
    print(*a)
    for i in range(len(a) - 1):
        a = [abs(a1 - a0) for a0, a1 in zip(a, a[1:])]
        print(' ' * i, *a)


def first(aaa):
    aaa = list(map(int, aaa))
    aaa = [abs(a1 - a0) for a0, a1 in zip(aaa, aaa[1:])]
    return aaa


def last(aaa):
    for i in range(len(aaa) - 1):
        aaa = [abs(a1 - a0) for a0, a1 in zip(aaa, aaa[1:])]
    return aaa[0]


def prepare():
    # for v in product([0, 1, 2], repeat=10):
    ret = [0] * (3 ** 10)
    for i in range(3 ** 10):
        v = i
        v, m1 = divmod(v, 3)
        tmp = []
        for _ in range(9):
            v, m2 = divmod(v, 3)
            tmp.append(abs(m1 - m2))
            m1 = m2
        tmp.reverse()
        for _ in range(8):
            tmp = [abs(a1 - a0) for a0, a1 in zip(tmp, tmp[1:])]
        ret[i] = tmp[0]
    return ret


# test([2, 3, 1, 1, 3, 1, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 2, 2, 3, 1, 2])
# test([2, 3, 1, 1, 3, 3, 2, 3, 1, 2])
# test([1, 3, 1, 3, 1, 3, 1, 3, 1, 3])

n = int(input())
aaa = input()
aaa = first(aaa)
ppp = prepare()
pow3 = [3 ** (9 - i) for i in range(10)]
while len(aaa) >= 10:
    aaa = [ppp[sum(map(mul, zip(aaa[i:i + 10], pow3)))] for i in range(len(aaa) - 9)]
ans = last(aaa)
print(ans)
Problem p02831 (python)

Fixed submission:
from fractions import gcd

a, b = map(int, input().split())
print(a * b // gcd(a, b))

Buggy submission (verdict: Runtime Error):
import fraction
a, b = map(int, input().split())
print(a * b // fraction.gcd(a, b))
Problem p02834 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u):
    ans = 0
    catch = self_depths[u] // 2
    while self_depths[u] > catch:
        ans = max(ans, self_depths[u] + subtree_depths[u] - 1)
        u = parents[u]
    return ans


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
# print(parents)
# print(self_depths)
# print(subtree_depths)
print(solve(u))

Buggy submission (verdict: Runtime Error):
import sys


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u, v):
    ans = 0
    catch = self_depths[u] // 2
    while self_depths[u] > catch:
        ans = max(ans, self_depths[u] + subtree_depths[u] - 1)
        u = parents[u]
    return ans


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
# print(parents)
# print(self_depths)
# print(subtree_depths)
print(solve(u, v))

Buggy submission (verdict: Runtime Error):
import sys


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u, v):
    ans = 0
    while u != v:
        ans = max(ans, self_depths[u] + subtree_depths[u] - 1)
        u = parents[u]
    return ans


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
# print(parents)
# print(self_depths)
# print(subtree_depths)
print(solve(u, v))
Problem p02862 (python)

Fixed submission:
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


def solve(x, y):
    d, m = divmod(x + y, 3)
    if m != 0 or x / y > 2 or y / x > 2:
        return 0
    c = abs(d - x)

    MOD = 10 ** 9 + 7
    f, invs = prepare(d, MOD)
    return f * invs[c] * invs[d - c] % MOD


x, y = map(int, input().split())
print(solve(x, y))

Buggy submission (verdict: Runtime Error):
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


def solve(x, y):
    d, m = divmod(x + y, 3)
    if m != 0:
        return 0
    c = abs(d - x)

    MOD = 10 ** 9 + 7

    f, invs = prepare(d, MOD)

    return f * invs[c] * invs[d - c] % MOD


x, y = map(int, input().split())
print(solve(x, y))
Problem p03034 (python)

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

ans = 0
for c in range(1, n // 2):
    a = n - 1 - c
    k = c
    tmp = 0
    while a > c and a != k and a + c != k:
        tmp += sss[a] + sss[k]
        ans = max(ans, tmp)
        a -= c
        k += c
print(ans)

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


def score(cache, sss, a, ab, d):
    mat = cache[ab]
    if mat is None:
        mat = cache[ab] = np.cumsum(np.resize(sss, ((n - 1) // ab + 1, ab)).T, axis=1)
    mat_a = mat[a % ab]
    return mat[0][d] + mat_a[-1] - mat_a[-d - 2]


n = int(input())
sss = list(map(int, input().split()))
sss.extend([0] * n)
sss = np.array(sss, dtype=np.int64)

ans = 0
cache = [None] * n
for ab in range(1, int((n - 2) ** 0.5) + 1):
    for remain in range(ab, n - 3, ab):
        a = n - remain - 1
        d = remain // ab
        if remain < a:
            ans = max(ans, score(cache, sss, a, ab, d))
            if ab != d:
                ans = max(ans, score(cache, sss, a, d, ab))
        else:
            if a % ab > 0:
                ans = max(ans, score(cache, sss, a, ab, d))
            if a > d and ab != d and a % d > 0:
                ans = max(ans, score(cache, sss, a, d, ab))
print(ans)
Problem p03055 (python)

Fixed submission:
import sys

sys.setrecursionlimit(2 * 10 ** 5 + 5)


def dfs(v, p, links):
    farthest_d = 0
    farthest_v = v

    for u in links[v]:
        if u == p:
            continue
        res_d, res_v = dfs(u, v, links)
        if res_d > farthest_d:
            farthest_d = res_d
            farthest_v = res_v
    return farthest_d + 1, farthest_v


def solve(n, links):
    if n == 1:
        return True

    d, v = dfs(0, -1, links)
    d, v = dfs(v, -1, links)
    if (d + 1) % 3 == 0:
        return False
    return True


n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('First' if solve(n, links) else 'Second')

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(2 * 10 ** 5)


def dfs(v, p, links):
    farthest_d = 0
    farthest_v = v

    for u in links[v]:
        if u == p:
            continue
        res_d, res_v = dfs(u, v, links)
        if res_d > farthest_d:
            farthest_d = res_d
            farthest_v = res_v
    return farthest_d + 1, farthest_v


def solve(n, links):
    if n == 1:
        return True

    d, v = dfs(0, -1, links)
    d, v = dfs(v, -1, links)
    if (d + 1) % 3 == 0:
        return False
    return True


n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('First' if solve(n, links) else 'Second')
Problem p03057 (python)

Fixed submission:
def solve(n, m, s):
    f = s[0]
    MOD = 10 ** 9 + 7
    INF = 10 ** 6

    p = None
    seq = 0
    min_seq = INF
    for c in s:
        if c == p:
            seq += 1
        else:
            if p == f and (min_seq == INF or seq % 2 == 1):
                min_seq = min(min_seq, seq)
            seq = 1
            p = c

    if min_seq == INF:
        a, b = 1, 0
        for _ in range(n - 2):
            a, b = (a + b) % MOD, a
        return (3 * a + b) % MOD

    if n % 2 == 1:
        return 0

    n2 = n // 2
    ms = min(n2, min_seq // 2 + 1)

    dp = [0] * (n2 + 1)
    dp[0] = 1
    acc, reject = 1, 0
    for i in range(1, n2 + 1):
        dp[i] = (acc - reject) % MOD
        acc = (acc + dp[i]) % MOD
        if i >= ms:
            reject = (reject + dp[i - ms]) % MOD

    ans = 0
    for d in range(1, ms + 1):
        ans = (ans + dp[n2 - d] * d * 2) % MOD

    return ans


n, m = map(int, input().split())
s = input()

print(solve(n, m, s))

Buggy submission (verdict: Runtime Error):
def solve(n, m, s):
    f = s[0]
    MOD = 10 ** 9 + 7

    p = None
    seq = 0
    max_seq = 0
    for c in s + '*':
        if c == p:
            seq += 1
        else:
            if p == f:
                max_seq = max(max_seq, seq)
            seq = 1
            p = c

    if max_seq == m:
        a, b = 1, 0
        for _ in range(n - 2):
            a, b = (a + b) % MOD, a % MOD
        return (3 * a + b) % MOD

    if n % 2 == 1:
        return 0

    ms = max_seq // 2 + 1

    dp = [0] * (n // 2 + 1)
    ap = [0] * (n // 2 + 1)
    dp[0] = 0
    ap[0] = 1
    for i in range(1, n // 2 + 1):
        j = max(-1, i - ms - 1)
        dp[i] = (ap[i - 1] - ap[j]) % MOD
        ap[i] = (ap[i - 1] + dp[i]) % MOD

    ans = 0
    for d in range(2, ms * 2 + 1, 2):
        ans = (ans + dp[(n - d) // 2] * d) % MOD

    return ans


n, m = map(int, input().split())
s = input()

print(solve(n, m, s))