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

Fixed submission:
from fractions import gcd

N = int(input())
a = [int(i) for i in input().split()]

L = []
R = []
L.append(a[0])
R.append(a[-1])

for i in range(N-2):
    L.append(gcd(L[-1], a[i+1]))
    R.append(gcd(R[-1], a[-(i+2)]))

ans = max(L[-1], R[-1])
for i in range(N-2):
    tmp = gcd(L[i], R[-(i+2)])
    if tmp > ans:
        ans = tmp

print(ans)

Buggy submission (verdict: Runtime Error):
from math import gcd
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    # セグ木は 1-indexed
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  # 2進数表記の長さ
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  # 兄弟の右なら
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  # 兄弟の左なら
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())

a = [int(i) for i in input().split()]

count=0
ans=0

for i in range(N):
    if a[i]<0:
        count+=1
    	a[i]=abs(a[i])

if count%2==0:
    ans=sum(a)

else:
    a.sort()
    ans=sum(a)-a[0]*2

print(ans)
Problem p03062 (python)

Fixed submission:
N = int(input())

a = [int(i) for i in input().split()]

count=0
ans=0

for i in range(N):
    if a[i]<0:
        count+=1
    a[i]=abs(a[i])

if count%2==0:
    ans=sum(a)

else:
    a.sort()
    ans=sum(a)-a[0]*2

print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]
 
count=0
ans=0
for i in range(N):
    if a[i]<0:
        c+=1        
    a[i]=abs(a[i])

if c%2==0:
    ans=sum(a)
else:
    a.sort()
    ans=sum(a)-a[0]

Buggy submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]
 
count=0
ans=0
for i in range(N):
    if a[i]<0:
        c+=1        
    a[i]=abs(a[i])

if c%2==0
    ans=sum(a)
else:
    a.sort()
    ans=sum(a)-a[0]

Buggy submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]

count=0
ans=0
for i in range(N):
    if a[i]<0:
        c+=1
        
a[i]=abs(a[i])
if c%2==0
    ans=sum(a)
else:
    a.sort()
    ans=sum(a)-a[0]

Buggy submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]

count=0
ans=0
for i in range(N):
    if a[i]<0:
        c+=1
        
a[i]=abs[i]
if c%2==0
    ans=sum(a)
else:
    a.sort()
    ans=sum(a)-a[0]
Problem p03283 (python)

Fixed submission:
# 累積和(1次元)を用いた解法
from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    LR_acc = []
    for L in LR:
        LR_acc.append(list(accumulate(L)))
    
    for p, q in query:
        ans = 0
        for i in range(p,q+1):
            ans += LR_acc[i][q] - LR_acc[i][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
# 桁dp + 二分探索
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def lunlun_num(N):
    N = str(N)
    L = len(N)

    dp = [[0]*10 for j in range(L)]
    for j in range(1,int(N[0])):
        dp[0][j] = 1

    flag = True
    for i in range(L-1):
        d = int(N[i+1])
        b = int(N[i])
        
        dp[i+1][0] += dp[i][0] + dp[i][1]
        dp[i+1][9] += dp[i][8] + dp[i][9]
        for j in range(1,9):
            dp[i+1][j] += dp[i][j-1] + dp[i][j] + dp[i][j+1]
        for j in range(1,10):
            dp[i+1][j] += 1

        if flag:
            if d < b - 1:
                flag = False
            elif d <= b + 1:
                for j in range(max(0, b-1),d):
                    dp[i+1][j] += 1
            else:
                for j in range(max(0, b-1),b+2):
                    dp[i+1][j] += 1
                    flag = False

    return sum(dp[L-1]) + 1 if flag else sum(dp[L-1])


def main():
    K = int(readline())

    # xを決め打って二分探索
    left = 0
    right = 10**10
    while left + 1 < right:
        x = (left + right) // 2

        if lunlun_num(x) >= K:
            right = x
        else:
            left = x
    
    print(right)


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

Fixed submission:
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def bfs(field, d, sx, sy, gx, gy):
    queue = deque([(sx, sy)])
    d[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (gx, gy):
            return d[x][y]

        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # field内かつ障害物じゃないかつ未訪問なら追加
            if (0 <= nx <= gx and 0 <= ny <= gy
                and field[nx][ny] != "#" 
                and d[nx][ny] == -1):
                d[nx][ny] = d[x][y] + 1
                queue.append((nx, ny))

def main():
    H,W = map(int, readline().split())
    s = [readline() for i in range(H)]

    #スタートからの距離(-1は未訪問)
    d = [[-1]*W for i in range(H)]

    min_path = bfs(s, d, 0, 0, H-1, W-1)
    if min_path is not None:
        min_path += 1
    else:
        print(-1)
        exit()

    black = 0
    for line in s:
        black += line.count("#")

    ans = H * W - min_path - black
    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def bfs(field, d, sx, sy, gx, gy):
    queue = deque([(sx, sy)])
    d[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (gx, gy):
            return d[x][y]

        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # field内かつ障害物じゃないかつ未訪問なら追加
            if (0 <= nx <= gx and 0 <= ny <= gy
                and field[nx][ny] != "#" 
                and d[nx][ny] == -1):
                d[nx][ny] = d[x][y] + 1
                queue.append((nx, ny))

def main():
    H,W = map(int, readline().split())
    s = [readline() for i in range(H)]

    #スタートからの距離(-1は未訪問)
    d = [[-1]*W for i in range(H)]

    min_path = bfs(s, d, 0, 0, H-1, W-1) + 1

    black = 0
    for line in s:
        black += line.count("#")

    ans = H * W - min_path - black
    print(ans)


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

Fixed submission:
import sys
from collections import deque

read = sys.stdin.buffer.read

N, *A = map(int, read().split())
A.sort(reverse=True)

deq = deque([A[0]])
ans = 0

for x in A[1:]:
    ans += deq.popleft()
    deq.append(x)
    deq.append(x)

print(ans)

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

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

A.sort(reverse=True)

deq = deque([A[0]])
ans = 0

for x in A[1:]:
    print(f"{deq=}, {x=}")
    ans += deq.popleft()
    deq.append(x)
    deq.append(x)

print(ans)
Problem p02630 (python)

Fixed submission:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    print(ans)

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

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop([B[i]])
    print(ans)
Problem p02642 (python)

Fixed submission:
from collections import Counter

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

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

# D[a] = True: Aにaより小さいaの約数が存在する
A_max = max(A)
dp = {a: False for a in A}

for a in A:
    # xが数列Aに含まれているとき、aより大きいaの倍数tについて、dp[a * t]をTrueに変更する
    if counter[a] > 0:
        t = 2
        while a * t <= A_max:
            dp[a * t] = True
            t += 1

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is False:
        ans += 1

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import Counter
import sympy

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

counter = Counter(A)

ans = 0
for k, v in counter.items():
    if v != 1:
        continue
    can = True
    for d in sympy.divisors(k):
        if d == k:
            continue
        if d in counter:
            can = False
    if can:
        ans += 1

print(ans)
Problem p02678 (python)

Fixed submission:
import queue

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

graph = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)

# 各部屋に設定する番号を記録する
v = [-1 for i in range(N)]  # 全頂点を「未訪問」に初期化
v[0] = 0  # スタート地点を0にする
# queueを作成し部屋1（インデックスは0）を入れる
q = queue.Queue()
q.put(0)

while not q.empty():
    # queueの先頭（今いる部屋の番号）を取り出す
    x = q.get()
    # 今いる部屋と繋がっている部屋を順に探索する
    for y in graph[x]:
        # -1 でない場合は探索済みなのでスキップする
        if v[y] != -1:
            continue
        # あとで探索するためにqueueに入れておく
        q.put(y)
        v[y] = x

print("Yes")
for i in range(1, N):
    print(v[i] + 1)

Buggy submission (verdict: Runtime Error):
import queue

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

graph = [[] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)

dist = [-1 for i in range(N)]
que = queue.Queue()

dist[0] = 0
que.put(0)


while not que.empty():
    v = que.get()
    for nv in graph[v]:
        if dist[nv] != -1:
            continue

        dist[nv] = dist[v] + 1
        que.push(nv)


print("Yes")
for i in range(1, N):
    print(v[i] + 1)
Problem p02696 (python)

Fixed submission:
import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())
x = min(B-1, N)
print(math.floor(A*x/B) - A*math.floor(x/B))

Buggy submission (verdict: Runtime Error):
import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())
x = min(B-1, N)
print(A*x/B - A*(X/B))
Problem p03544 (python)

Fixed submission:
N = int(input())

L = [None] * (N + 1)
L[0] = 2
L[1] = 1

for i in range(2, N + 1):
    L[i] = L[i - 1] + L[i - 2]

print(L[N])

Buggy submission (verdict: Runtime Error):
from typing import List


N = int(input())

L: List[int] = [None] * (N + 1)
L[0] = 2
L[1] = 1

for i in range(2, N + 1):
    L[i] = L[i - 1] + L[i - 2]

print(L[N])
Problem p03545 (python)

Fixed submission:
import sys


def dfs(i, s, val, formula):
    if (i == len(s) - 1):
        if val == 7:
            print(formula + "=7")
            sys.exit()
            return formula
        else:
            return None

    dfs(i + 1, s, val + int(s[i + 1]), formula + "+" + s[i + 1])
    dfs(i + 1, s, val - int(s[i + 1]), formula + "-" + s[i + 1])
    return None


s = input()
ans = dfs(0, s, int(s[0]), s[0])

Buggy submission (verdict: Runtime Error):
from typing import Optional
import sys


def dfs(i: int, s: str, val: int, formula: str) -> Optional[str]:
    if (i == len(s) - 1):
        if val == 7:
            print(formula + "=7")
            sys.exit()
            return formula
        else:
            return None

    dfs(i + 1, s, val + int(s[i + 1]), formula + "+" + s[i + 1])
    dfs(i + 1, s, val - int(s[i + 1]), formula + "-" + s[i + 1])
    return None


s = input()
ans = dfs(0, s, int(s[0]), s[0])
Problem p03944 (python)

Fixed submission:
import numpy as np

W, H, N = map(int, input().split())

area = np.ones((W, H))

for _ in range(N):
    x, y, a = map(int, input().split())

    if a == 1:
        area[:x, :] = 0
    elif a == 2:
        area[x:, :] = 0
    elif a == 3:
        area[:, :y] = 0
    elif a == 4:
        area[:, y:] = 0

print(int(np.sum(area)))

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

W, H, N = map(int, input().split())

area = np.ones((W, H))

for _ in range(N):
    x, y, a = map(int, input().split())

    if a == 1:
        area[:x, :] = 0
    elif a == 2:
        area[x:, :] = 0
    elif a == 3:
        area[:, :y] = 0
    elif a == 4:
        area[:, y:] = 0

print(int(np.sum(area)))
Problem p02660 (python)

Fixed submission:
import math
import collections

n = int(input())
s = 0
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

m = 0
l = collections.Counter(prime_factorize(n))
l2 = list(dict.values(l))
#for i in range(len(l2)):
#    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)
for i in range(len(l2)):
    for j in range(n):
        if l2[i] >= j*(j+1)/2:
            m = j
        else:
            break


    s += m


print(s)

Buggy submission (verdict: Runtime Error):
import sympy
import math
n = int(input())
s = 0
l  = sympy.factorint(n)
l2 = list(dict.values(l))
for i in range(len(l2)):
    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)

print(s)

Buggy submission (verdict: Runtime Error):
import sympy
import math
n = int(input())
s = 0
l  = sympy.factorint(n)
l2 = list(dict.values(l))
for i in range(len(l2)):
    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)

print(s)
Problem p02696 (python)

Fixed submission:
A,B,N = map(int,input().split())
S = 0
n = N // B
r = N % B
if B > N:
    S = (A*N)//B
else:
    if  r == 0:
        S = (A*(N-1))//B - A * ((N-1)//B)
    elif r == B - 1:
        S = (A*N)//B - A * (N//B)
    else:
        S = (A*(n*B-1))//B - A * ((n*B-1)//B)

print(S)

Buggy submission (verdict: Runtime Error):
A,B,N = map(int,input().split())
S = 0
n = N // B
r = N % B
if B > N:
    S = (A*N)//B
else:
    if  r == 0:
        S = (A*(N-1))//B - A * ((N-1)//B))
    elif r == B - 1:
        S = (A*N)//B - A * (N//B)
    else:
        S = (A*(n*B-1))//B - A * ((n*B-1)//B)

print(S)

Buggy submission (verdict: Runtime Error):
A,B,N = map(int,input().split())
S = 0
n = N // B
r = N % B
if B > N:
    S = (A*N)//B
else:
    if  r == 0:
        S = (A*(N-1))//B - A * ((N-1）//B))
    elif r == B - 1:
        S = (A*N)//B - A * (N//B)
    else:
        S = (A*(n*B-1))//B - A * ((n*B-1)//B)

print(S)

Buggy submission (verdict: Runtime Error):
A,B,N = map(int,input().split())
S = 0
n = N // B
r = N % B
if B > N:
    S = (A*N)//B
else:
    if  r == 0:
        S = (A*(N-1))//B - A * ((N-1）//B))
    elif r == B - 1:
        S = (A*N)//B - A * (N//B)
    else:
        S = (A*(n*B-1))//B - A * ((n*B-1)//B)

print(S)

Buggy submission (verdict: Runtime Error):
A,B,N = map(int,input().split())
S = 0
n = N // B
if B <= N:
    for i in range(1,n+1):
        l = i * B  - 1
        while S < max(S,(A*l)//B - A * (l//B))
        S = max(S,(A*l)//B - A * (l//B))
else:
    S = (A*N)//B
print(S)
Problem p02717 (python)

Fixed submission:
A, B, C = input().split()
print(C, A ,B)

Buggy submission (verdict: Runtime Error):
A, B, C = input().split()  
print(C A B)
Problem p02730 (python)

Fixed submission:
S = input()
N = len(S)
P = 0
for i in range ((N-1)//2):
    if S[i] == S[N-1-i]:
        for k in range((N-1)//2):
            if S[k] == S[((N-3)//2)-k] and S[((N+1)//2)+k] == S[N-1-k]:
                P = P
            else:
                P += 1
    else:
        P += 1

if P == 0:
    print('Yes')
else:
    print('No')

Buggy submission (verdict: Runtime Error):
S = input()
N = len(S)
P = 0
for i in range (N-1//2):
    if S[i] == S[N-1-i]:
        for k in range(N-1//2):
            if S[k] == S[((N-1)//2)-k] and S[((N+1)//2)+k] == S[N-1-k]:
                P = P
            else:
                P += 1
        else:
            P += 1

if P == 0:
    print('Yes')
else:
    print('No')
Problem p02802 (python)

Fixed submission:
N , M = map(int,input().split())
p = [''] * M
S = [''] * M
A = [0] * N
W = [0] * N
for i in range(M):
    p[i],S[i] = map(str,input().split())
    p[i] = int(p[i])
    if A[p[i]-1] == 0:
        if S[i] == 'WA':
            W[p[i]-1] += 1
        else:
            A[p[i]-1] += 1

for j in range(N):
    if A[j] == 0:
        W[j] =0
print(sum(A),sum(W))

Buggy submission (verdict: Runtime Error):
N , M = map(int,input().split())
p = [''] * M
S = [''] * M
A = [0] * N
W = [0] * N
for i in range(M):
    p[i],S[i] = map(str,input().split())
    p[i] = int(p[i])
    if A[p[i]-1] == 0:
        if S[i] == 'WA':
            W[p[i]-1] += 1
        else:
            A[p[i]-1] += 1

for j in range(N):
    if A[j] == 0:
        W[j] =0
 print(sum(A),sum(W))
Problem p03037 (python)

Fixed submission:
N, M = map(int, input().split())
L = [0] * M
R = [0] * M
min = 1
max = N
X = 0
for i in range(M):
    L[i], R[i] = map(int, input().split())
    if L[i] > min:
        min = L[i]
    if R[i] < max:
        max = R[i]
    if R[i] < min or L[i] > max:
        X +=1


if X == 0:
    print(max-min+1)
else:
    print(0)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
L = [0] * M
R = [0] * M
min = 1
max = N
X = 0
for i in range(M):
    L[i], R[i] = map(int, input().split())
    if L[i] > min:
        min = L[i]
    if R[i] < max:
        max = R[i]
    if R[i] < min or L[i] > max:
        X +=1


if X = 0:
    print(max-min+1)
else:
    print(0)
Problem p03085 (python)

Fixed submission:
ans = {}
ans['A'] = 'T'
ans['T'] = 'A'
ans['C'] = 'G'
ans['G'] = 'C'


s = input()
print(ans[s])

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
MOD = 1000000007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)
Problem p03088 (python)

Fixed submission:
from functools import lru_cache
MOD = 1000000007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
MOD = 1000_000_007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)
Problem p03263 (python)

Fixed submission:
H, W = [int(i) for i in input().split()]
A = [[]] * H
for i in range(H):
    A[i] = [int(i) for i in input().split()]

ans = []
x = -1
for i in range(H):
    x = x * (-1)
    l, r, d = (0, W, 1) if i % 2 == 0 else (W-1, -1, -1)
    for j in range(l, r, d):
        #print("i,j=",i, j)
        if A[i][j] % 2 == 0:
            continue
        if x == 1 and i == H - 1 and j == W - 1:
            continue
        if x == -1 and i == H - 1 and j == 0:
            continue
        
        if not(j + x < 0 or j + x >= W):
            A[i][j] = A[i][j] - 1
            A[i][j + x] = A[i][j + x] + 1
            ans.append((i, j, i, j+x))
        else :
            A[i][j] = A[i][j] - 1;
            A[i+1][j] = A[i+1][j] + 1
            ans.append((i, j, i+1, j));


print (len(ans))
for y, x, b, a in ans:
    print (y+1, x+1, b+1, a+1)

Buggy submission (verdict: Runtime Error):
H, W = [int(i) for i in input().split()]
A = [[]] * H
for i in range(H):
    A[i] = [int(i) for i in input().split()]

ans = []
x = -1
for i in range(H):
    x = x * (-1)
    l, r, d = (0, W, 1) if i % 2 == 0 else (W-1, -1, -1)
    for j in range(l, r, d):
        #print("i,j=",i, j)
        if A[i][j] % 2 == 0:
            continue
        if x == 1 and i == H - 1 and j == W - 1:
            continue
        if x == -1 and i == 0 and j == 0:
            continue
        
        if not(j + x < 0 or j + x >= W):
            A[i][j] = A[i][j] - 1
            A[i][j + x] = A[i][j + x] + 1
            ans.append((i, j, i, j+x))
        else :
            A[i][j] = A[i][j] - 1;
            A[i+1][j] = A[i+1][j] + 1
            ans.append((i, j, i+1, j));


print (len(ans))
for y, x, b, a in ans:
    print (y+1, x+1, b+1, a+1)

Buggy submission (verdict: Runtime Error):
H, W = [int(i) for i in input().split()]
A = [[]] * H
for i in range(H):
    A[i] = [int(i) for i in input().split()]

ans = []
x = -1
for i in range(H):
    x = x * (-1)
    l, r, d = (0, W, 1) if i % 2 == 0 else (W-1, -1, -1)
    for j in range(l, r, d):
        #print("i,j=",i, j)
        if A[i][j] % 2 == 0:
            continue
        if x == 1 and i == H - 1 and j == W - 1:
            continue
        if x == -1 and i == 0 and j == 0:
            continue
        
        if not(j + x < 0 or j + x >= W):
            A[i][j] = A[i][j] - 1
            A[i][j + x] = A[i][j + x] + 1
            ans.append((i, j, i, j+x))
        else :
            A[i][j] = A[i][j] - 1;
            A[i+1][j] = A[i+1][j] + 1
            ans.append((i, j, i+1, j));


print (len(ans))
for y, x, b, a in ans:
    print (y, x, b, a)