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

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
pys = []
for i in range(m):
    x = na()
    x = [x[0], x[1], i]
    pys.append(x)

pys.sort()
pp = -1
lid = 0
ans = [0] * m
for i in range(m):
    if pys[i][0] == pp:
        lid += 1
    else:
        lid = 1
    ans[pys[i][2]] = pys[i][0] * 1000000 + lid
    pp = pys[i][0]
for v in ans:
    print("{:012d}".format(v))

Buggy submission (verdict: Runtime Error):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
pys = []
for i in range(m):
    x = na()
    x = [x[0], x[1], i]
    pys.append(x)

pys.sort()
pp = -1
lid = 0
ans = [0] * m
for i in range(m):
    if pys[i][0] == pp:
        lid += 1
    else:
        lid = 1
    ans[pys[i][2]] = pys[i][0] * 1000000 + lid
    pp = pys[i][0]
for v in ans:
    print(f"{v:012d}")
Problem p03634 (python)

Fixed submission:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
from queue import Queue
qs = Queue()
qs.put(k)
dw[k] = 0

while not qs.empty():
    cur = qs.get()
    for e in g[cur]:
        if e[0] != par[cur]:
            par[e[0]] = cur
            dw[e[0]] = dw[cur] + e[1]
            qs.put(e[0])


# dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100001)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])

Buggy submission (verdict: Runtime Error):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
g = []
for i in range(n+1): g.append([])

for i in range(n-1):
    a, b, c = na()
    g[a].append((b,c))
    g[b].append((a,c))

q,k = na()

def dfs(cur, pre, g, par, dw, w):
    dw[cur] = w
    par[cur] = pre
    for e in g[cur]:
        if e[0] != pre:
            dfs(e[0], cur, g, par, dw, w + e[1])

par = [-1] * (n+2)
dw = [-1] * (n+2)
dfs(k, -1, g, par, dw, 0)

for z in range(q):
    x, y = na()
    print(dw[x] + dw[y])
Problem p02990 (python)

Fixed submission:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(it):
    return sum(1 for _ in it)


def solve():
    """
    C[N-K+1][i]*C[K-1][i-1]
    1 1 1
    1 2 3
    1 3 6
    """
    N, K = read_ints()
    C = [
        [0 for _ in range(2002)] for _ in range(2002)
    ]
    modulo = 10**9+7
    C[1][1] = 1
    for i in range(2, 2002):
        for j in range(1, i+1):
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%modulo

    for i in range(1, K+1):
        print((C[N-K+1+1][i+1]*C[K-1+1][i-1+1])%modulo)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def ilen(it):
    return sum(1 for _ in it)


def solve():
    """
    C[N-K+1][i]*C[K-1][i-1]
    1 1 1
    1 2 3
    1 3 6
    """
    N, K = read_ints()
    C = [
        [0 for _ in range(2001)] for _ in range(2001)
    ]
    modulo = 10**9+7
    C[1][1] = 1
    for i in range(2, 2001):
        for j in range(1, i+1):
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%modulo

    for i in range(1, K+1):
        print((C[N-K+1+1][i+1]*C[K-1+1][i-1+1])%modulo)


if __name__ == '__main__':
    solve()
Problem p02699 (python)

Fixed submission:

f=0
    # n=int(input())
    # a=list(map(int,input().split()))
    # c,d=map(int,input().split())
    
s,w=map(int,input().split())
if(s<=w):
    print("unsafe")
else:
    print("safe")





# print("Yes" if f==1 else "No")

Buggy submission (verdict: Runtime Error):

f=0
    # n=int(input())
    # a=list(map(int,input().split()))
    # c,d=map(int,input().split())
    
    s,w=map(int,input().split())
    if(s<=w):
        print("unsafe")
    else:
        print("safe")
    




# print("Yes" if f==1 else "No")
Problem p02771 (python)

Fixed submission:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College
    Date:24/03/2020
'''

def main():
    
    # for _ in range(ii()):
    
    a=list(map(int,input().split()))
    if(len(set(a))==2):
        print('Yes')
    else:
        print('No')
        
















    
    
if __name__ =="__main__":
    main()

Buggy submission (verdict: Runtime Error):
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineerin College
    Date:24/03/2020
'''
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
def main():
    
    # for _ in range(ii()):
    
    a=li()
    if(len(set(a))==2):
        print('Yes')
    else:
        print('No')
        
















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

Fixed submission:
from math import ceil
N,K = map(int,input().split())
A=list(map(int,input().split()))


low=0
high=10**9+1

while low<=high:
    mid=(low+high)//2
    if mid==0:
        print(1)
        exit()

    cnt=0
    for a in A:
        if a<=mid:
            continue
        v=ceil(a/mid)
        cnt+=v-1

    if cnt<=K:
        high=mid-1
    else:
        low=mid+1
print(low)

Buggy submission (verdict: Runtime Error):
from math import ceil
N,K = map(int,input().split())
A=list(map(int,input().split()))


low=0
high=10**9+1

while low<=high:
    mid=(low+high)//2
    cnt=0
    for a in A:
        if a<=mid:
            continue
        v=ceil(a/mid)
        cnt+=v-1

    if cnt<=K:
        high=mid-1
    else:
        low=mid+1
print(low)

Buggy submission (verdict: Runtime Error):
from math import ceil
N,K = map(int,input().split())
A=list(map(int,input().split()))


low=0
high=10**9+1

while low<=high:
    #答え(全てをmid以下の長さにできるならOK)
    mid=(low+high)//2
    cnt=0
    for a in A:
        v=ceil(a/mid)
        cnt+=max(v-1,0)

    if cnt<=K:
        high=mid-1
    else:
        low=mid+1
print(low)
Problem p02627 (python)

Fixed submission:
X=input()
if X==X.lower():
    print("a")
else:
    print("A")

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

if X==X.lower():
    print("a")
else:
    print("A")
Problem p02629 (python)

Fixed submission:
N = int(input())
s=1
while pow(26,s)<N:
    N-=pow(26,s)
    s+=1


N-=1
ans=["a"]*s
for i in range(s):
    r = N%26
    ans[i] = chr(ord(ans[i])+r)
    N//=26

#if ans[0]=="a":
#    ans[0]="z"
#else:
#    ans[0] = chr(ord(ans[0])+1)
print("".join(reversed(ans)))

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

ans=""
while N:
    r=(N+26-1)%26
    ans+=chr(ord("a")+r)
    N//=26
ans=list(reversed(ans))

if ans[-1]=="z":
    ans[-1]="a"
else:
    ans[-1] = chr(ord(ans[-1])+1)
print("".join(map(str,ans)))
Problem p02659 (python)

Fixed submission:
from math import floor
A,B = input().split()
B="".join(B.split("."))
A=int(A)
B=int(B)
print(int(A*B//100))

Buggy submission (verdict: Runtime Error):
from math import floor
A = int(input())
B = float(input())
print(floor(A*B))

Buggy submission (verdict: Runtime Error):
from math import floor
A,B =input().split()
A = int(input())
B = float(input())
print(floor(A*B))
Problem p02689 (python)

Fixed submission:
N,M = map(int,input().split())
H = list(map(int,input().split()))
adj=[set() for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    adj[a].add(b)
    adj[b].add(a)


ans=0
for i in range(N):
    if len(adj[i])==0:
        ans+=1
    elif all([H[i]>H[v] for v in adj[i]]):
        ans+=1
print(ans)

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

def ok(B):
    i=1
    B=abs(B)
    while i**5<B:
        i+=1
    return i**5==B

def get(B):
    f = B/abs(B)
    i=1
    B=abs(B)
    while i**5<B:
        i+=1
    return int(i*f)



A_cand=[]
i=0
while i**5<=10**10:
    A_cand.append(i)
    i+=1

#print(A_cand)
for a in range(300):
    B_5=a**5-X
    if ok(B_5):
        r=get(B_5)
        print(a,r)
        exit()
        break
Problem p02699 (python)

Fixed submission:
S,W = map(int,input().split())
if W>=S:
    print("unsafe")
else:
    print("safe")

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
S = input()
N = len(S)

D=defaultdict()
prev=0
ans=0
for i,s in enumerate(reversed(S)):
    cur=prev+pow(10,i,2019)*int(s)%2019
    ans+=D[cur]
    D[cur]+=1
    prev=cur
print(ans)
Problem p02777 (python)

Fixed submission:
S,T = map(str,input().split())
X,Y = map(int,input().split())
Z = input()
if S==Z:
  print(X-1,Y)
elif T==Z:
    print(X,Y-1)
else:
    print(X,Y)

Buggy submission (verdict: Runtime Error):
S,T = map(input().split())
X,Y = map(int,input().split())
Z = input()
if S==Z or T==Z:
    print(X+Y-1)
else:
    print(X+Y)
Problem p02792 (python)

Fixed submission:
N = int(input())

C = [[0]*10 for _ in range(10)]
for n in range(1, N+1):
    s = str(n)
    C[int(s[0])][int(s[-1])] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += C[i][j]*C[j][i]
print(ans)

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

C = [[0]*10 for _ in range(10)]
for n in range(1, N+1):
    s = str(n)
    C[int[s[0]]][int[s[-1]]] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += C[i][j]*C[j][i]
print(ans)
Problem p02829 (python)

Fixed submission:
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(ans.pop())

Buggy submission (verdict: Runtime Error):
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
assert len(ans)==1
print(int(ans[0]))

Buggy submission (verdict: Runtime Error):
A=int(input())
B=int(input())
ans={1,2,3}-{A,B}
print(int(ans))
Problem p02833 (python)

Fixed submission:
def solve():
    _N = int(input())
    N = _N
    ans = 0
    if N % 2 == 0:
        div = 10
        while N // div > 0:
            ans += N//div
            div *= 5
    print(ans)


solve()

Buggy submission (verdict: Runtime Error):
from math import ceil
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = [v]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.append(next)
    Q = tmp

dst_u = -1
# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = [u]
while Q:
    tmp = []
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 >= dist_from_v[next]:
                    # print("update")
                    cut = (cur, next)
                else:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_u_dst = max(dist_from_u)
dist_v_dst = dist_from_v[dst_u]
# print(dist_from_v)
# print(dist_from_u)
# print(cut)
assert dist_u_dst < dist_v_dst

if dist_v_dst % 2 == 0:
    ans = dist_u_dst+(dist_v_dst-dist_u_dst)//2
else:
    ans = dist_u_dst+dist_v_dst-dist_u_dst
print(ans)
Problem p02834 (python)

Fixed submission:
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next] or True:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.add(next)
    Q = tmp

ans = 0
for i in range(N):
    if dist_from_u[i] < dist_from_v[i]:
        ans = max(ans, dist_from_v[i]-1)
print(ans)
exit()

dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Buggy submission (verdict: Runtime Error):
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)
Problem p02860 (python)

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

if N%2==0 and all(a==b for a,b in zip(S,S[N//2:])):
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
N=int(input())
S=input()
if all(a==b for a,v in zip(S,S[N:]):
       print("Yes")
else:
       print("No")
Problem p02880 (python)

Fixed submission:
N=int(input())
for i in range(1,10):
  for j in range(i,10):
    if i*j==N:
      print("Yes")
      exit()
print("No")

Buggy submission (verdict: Runtime Error):
N=int(input())
for i in range(1,10):
  for j in range(i,10):
    if i*j==N:
      print("Yes")
   	  exit()
print("No")
Problem p02933 (python)

Fixed submission:
B=int(input())
S=input()
if B>=3200:
  print(S)
else:
  print("red")

Buggy submission (verdict: Runtime Error):
N=int(input())
S=input()
if B<3200:
  print(S)
else:
  print("red")
Problem p02984 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

sum_odd = sum([v for v in A[1::2]])
x0 = sum(A)-2*sum_odd
ans = [x0]

x = x0
for a in A:
    nex = 2*a-x
    ans.append(nex)
    x = nex
print(*ans[:-1])

Buggy submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))


low=0
high=10**10

#binary search the value of rain onto Mountain1
while low<=high:
    mid=(low+high)//2

    cur=mid
    for i,a in enumerate(A):
        cur=a-cur
        if cur<0:#途中で足りなくなったら、midが大きすぎ
            break
       #break
    if cur>=mid:
        low=mid+1
    else:
        if i%2==0:
            low=mid+1
        else:
          	high=mid-1
            low=mid+1


ans=[]
cur=high
for a in A:
    ans.append(cur*2)
    cur=a-cur
print(" ".join(map(str,ans)))

Buggy submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))


low=0
high=10**9*2

#binary search the value of rain onto Mountain1
while low<=high:
    mid=(low+high)//2

    cur=mid
    for a in A:
        cur=a-cur
        if cur<0:#途中で足りなくなったら、midが大きすぎ
            break
       #break
    if cur>=mid:
        low=mid+1
    else:
        high=mid-1


ans=[]
cur=high
for a in A:
    ans.append(cur*2)
    cur=a-cur
assert cur==high
print(" ".join(map(str,ans)))
Problem p02987 (python)

Fixed submission:
from collections import Counter
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

S = input()[:-1]
C = Counter(S)
if all([v == 2 for key, v in C.items()]):
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
from collections import Counter
input = sys.stdin.readline

S=input[:-1]
C=Counter(S)
if all([v==2 for key,v in C.items()]):
    print("Yes")
else:
    print("No")
Problem p03003 (python)

Fixed submission:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())

# Sのi文字目までと、Tのj文字目までで、dp[i][j]こ
dp = [[0]*(M+1) for _ in range(N+1)]

for r in range(1, N+1):
    for k in range(1, M+1):
        if S[r-1] == T[k-1]:
            dp[r][k] = 1+dp[r-1][k]+dp[r][k-1]
            dp[r][k] %= MOD
        else:
            dp[r][k] = dp[r-1][k]+dp[r][k-1]-dp[r-1][k-1]
            dp[r][k] %= MOD
print((dp[-1][-1]+1) % MOD)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())

# Sのi文字目までと、Tのj文字目までで、dp[i][j]こ
dp = [[0]*(N+1) for _ in range(M+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1+dp[i-1][j]+dp[i][j-1]
            dp[i][j] %= MOD
        else:
            dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            dp[i][j] %= MOD
print((dp[-1][-1]+1) % MOD)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())

# Sのi文字目までと、Tのj文字目までで、dp[i][j]こ
dp = [[0]*(N+1) for _ in range(M+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1+dp[i-1][j]+dp[i][j-1]
            dp[i][j] %= MOD
        else:
            dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]
            dp[i][j] %= MOD
print((dp[-1][-1]+1) % MOD)
Problem p03015 (python)

Fixed submission:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve2():
    L = input()[:-1]
    int_L = int(L, 2)
    ans = 1  # (0,0)のぶん
    for l in range(1, int_L+1):  # 10**6
        bit_cnt = bin(l).count("1")  # 遅そうO(len(bin(l)))
        ans += pow(2, bit_cnt, MOD)
        ans %= MOD
    print(ans)


def solve3():
    L = input()[:-1]
    # dp[smaller?][上からi桁目まで見た] = 何通りあるか?
    dp = [[0]*2 for _ in range(len(L)+1)]
    dp[0][0] = 1  # 0

    for i, c in enumerate(L):
        dp[i+1][0] = dp[i][0]*(int(c)+1)
        dp[i+1][1] = dp[i][1]*3+dp[i][0]*int(c)

        dp[i+1][0] %= MOD
        dp[i+1][1] %= MOD
    print(sum(dp[-1]) % MOD)


solve3()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve3():
    L = input()[:-1]
    # dp[smaller?][上からi桁目まで見た] = 何通りあるか?
    dp = [0]*2
    dp[0] = 1  # 0

    for i, c in enumerate(L):
        tmp = [0]*2
        tmp[0] = dp[0]*(int(c)+1)
        tmp[1] = dp[1]*3+dp[0]*int(c)

        tmp[0] %= MOD
        tmp[1] %= MOD
        dp = tmp
    print(sum(dp[-1]) % MOD)


solve3()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve2():
    L = input()[:-1]
    int_L = int(L, 2)
    ans = 1  # (0,0)のぶん
    for l in range(1, int_L+1):  # 10**6
        bit_cnt = bin(l).count("1")  # 遅そうO(len(bin(l)))
        ans += pow(2, bit_cnt, MOD)
        ans %= MOD
    print(ans)


def solve3():
    L = input()[:-1]
    # dp[smaller?][上からi桁目まで見た] = 何通りあるか?
    dp = [0]*2
    dp[0][0] = 1  # 0

    for i, c in enumerate(L):
        tmp = [0]*2
        tmp[0] = dp[0]*(int(c)+1)
        tmp[1] = dp[1]*3+dp[0]*int(c)

        tmp[0] %= MOD
        tmp[1] %= MOD
        dp = tmp
    print(sum(dp[-1]) % MOD)


solve3()
Problem p03017 (python)

Fixed submission:
# python template for atcoder1
import sys

N, A, B, C, D = map(int, input().split())
L = list([v for v in input()])

HOP = [1, 2]
dp_d = [0]*N
dp_d[B-1] = 1
for i in range(N):
    if L[i] == "#":
        continue
    for h in HOP:
        dst = i+h
        if dst < N and L[dst] == ".":
            dp_d[dst] = max(dp_d[dst], dp_d[i])
dp_c = [0]*N
dp_c[A-1] = 1
for i in range(N):
    if L[i] == "#":
        continue
    for h in HOP:
        dst = i+h
        if dst < N and L[dst] == ".":
            dp_c[dst] = max(dp_c[dst], dp_c[i])
reachable = False
if dp_c[C-1] == 1 and dp_d[D-1] == 1:
    reachable = True

if not reachable:
    print("No")
elif C < D:
    print("Yes")
else:
    if "..." in "".join(L[B-2:min(C, D)+1]):
        print("Yes")
    else:
        print("No")

Buggy submission (verdict: Runtime Error):
# python template for atcoder1
import sys

N, A, B, C, D = map(int, input().split())
L = list([v for v in input()])

HOP = [1, 2]
dp_d = [0]*N
dp_d[B-1] = 1
for i in range(N):
    if L[i] == "#":
        continue
    for h in HOP:
        dst = i+h
        if dst < N and L[dst] == ".":
            dp_d[dst] = max(dp_d[dst], dp_d[i])
dp_c = [0]*N
dp_c[A-1] = 1
for i in range(N):
    if L[i] == "#":
        continue
    for h in HOP:
        dst = i+h
        if dst < N and L[dst] == ".":
            dp_c[dst] = max(dp_c[dst], dp_c[i])
reachable = False
if dp_c[C-1] == 1 and dp_d[D-1] == 1:
    reachable = True

if not reachable:
    print("No")
elif C < D:
    print("Yes")
else:
    if "..." in "".join(L[B-2:min(C, D)]):
        print("Yes")
	e;se:
      print("No")
Problem p03038 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
L = list(map(int, input().split()))
OP = [list(map(int, input().split())) for _ in range(M)]
heapq.heapify(L)
OP = sorted(OP, key=lambda x: x[1], reverse=True)
ans = 0

for m, n in OP:
    for _ in range(m):
        if L:
            head = heapq.heappop(L)
            if head < n:
                ans += n
            else:
                print(ans+sum(L)+head)
                exit()
        else:
            print(ans)
            exit()
print(ans+sum(L))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
L = list(map(int, input().split()))
OP = [list(map(int, input().split())) for _ in range(M)]
heapq.heapify(L)
OP = sorted(OP, key=lambda x: x[1], reverse=True)
ans = 0

for m, n in OP:
    for _ in range(m):
        head = heapq.heappop(L)
        if head < n:
            ans += n
        else:
            print(ans+sum(L)+head)
            exit()
print(ans)