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

Fixed submission:
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  a[i], b[i] = map(int,input().split())

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  
s = [0] + [1]*n

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  x,y = max(x,y),min(x,y)
  if x == y:
    ans.append(c)
    continue
  c -= s[x]*s[y]
  #print(c, "x")
  ans.append(c)
  s[x] += s[y]
  #s[y] = 0
  for i in g[y]:
    d[i] = x
  g[x] += g[y]
  #g[y] = []
for t in ans[::-1]:
  print(t)

Buggy submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  a[i], b[i] = map(int,input().split())

d = list(range(n+1))
g = [[i] for i in range(n+1)]

c = n*(n-1)//2
ans = [c]

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  x,y = max(x,y),min(x,y)
  if x > y:
    c -= len(g[x])*len(g[y])
    for i in g[y]:
      d[i] = x
      g[x] += g[y]
  ans.append(c)

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

Buggy submission (verdict: Runtime Error):
,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  a[i], b[i] = map(int,input().split())

d = [0]*(n+1)
for i in range(1,n+1):
  d[i] = i
  
s = [0] + [1]*n

g=[ [0] ]*(n+1)
for i in range(1,n+1):
  g[i] = [i]
g[0] = []
#print(g)
#quit()

c = n*(n-1)//2
ans = []
ans.append(c)

for i in range(1,m)[::-1]:
  x = d[a[i]]
  y = d[b[i]]
  if x == y:
    ans.append(c)
    continue
  c -= s[x]*s[y]
  #print(c, "x")
  ans.append(c)
  s[x] += s[y]
  s[y] = 0
  for i in g[y]:
    d[i] = x
  g[x] = g[x] + g[y]
  g[y] = []
for t in ans[::-1]:
  print(t)
Problem p03252 (python)

Fixed submission:
s = input()
t = input()
while s != "":
  x = s[0]
  y = t[0]
  for i in range(len(s)):
    if (s[i] == x and t[i] != y) or (s[i] != x and t[i] == y):
      print("No")
      exit()
  s = s.replace(x,"")
  t = t.replace(y,"")
print("Yes")

Buggy submission (verdict: Runtime Error):
s = input()
t = input()
while s != "":
  x = s[0]
  y = t[0]
  for i in range(len(s)):
    if (s[i] == "x" and t[i] != "y") or (s[i] != "x" and t[i] == "y"):
      print("No")
      exit()
  s = s.replace(x,"")
  t = t.replace(y,"")
print("Yes")
Problem p03286 (python)

Fixed submission:
n = int(input())
s = ""
k = 0
while n!=0:
  if n%(2**(k+1)) == 2**k:
    if k%2 == 0:
      n -= 2**k
    else:
      n += 2**k
    s = "1"+s
  else:
    s = "0"+s
  k += 1

if s=="":
  s="0"

print("".join(s))

Buggy submission (verdict: Runtime Error):
n = int(input())
s =""
k = 0
while n!=0:
  if n%(2**(k+1)) == 2**k:
    if k%2 == 0:
      n -= 2**k
    else:
      n += 2**k
    s += "1"
  else:
    s += "0"
  k += 1

if s="":
  s="0"

print("".join(s))
Problem p03631 (python)

Fixed submission:
print("Yes" if int(input())%101 in range(0,100,10) else "No")

Buggy submission (verdict: Runtime Error):
print("YNeos"[if not int(input())%101 in range(0,100,10)::2])
Problem p02546 (python)

Fixed submission:
S = input()
if S[-1] == "s":
    print(S+"es")
else:
    print(S+"s")

Buggy submission (verdict: Runtime Error):
N,K = map(int,input().split())
l = []
mod = 998244353
for i in range(K):
    L,R = map(int,input().split())
    l.append([L,R])
l.sort()

a = [0 for i in range(N+1)]
a[1] = 1
b = [0 for i in range(N+1)]
b[1] = 1
for i in range(2,N+1):
    for j in range(K):
        if l[j][0] < i:
            a[i] += (b[i-l[j][0]]-b[max(0,i-l[j][1]-1)])%mod
        else:
            break
    b[i] = (b[i-1]+a[i])%mod
mod = 998244353
print(a[N]%mod)
Problem p02570 (python)

Fixed submission:
(d,t,s) = map(int,input().split())
if d > t*s:
    print("No")
else:
    print("Yes")

Buggy submission (verdict: Runtime Error):
import math


n = int(input())
a = [int(x) for x in input().split()]
l = [[] for i in range(n)]

def gcd(p,q):
    while q != 0:
        p = min(p%q,-(p%q)+q)
        p,q = q,p
    return p


g = a[0]
for i in range(1,n):
    g = gcd(g,a[i])

if g != 1:
    print("not coprime")

else:
    def fur(x):
        k = [1 for i in range(x+1000)]
        k[0]=k[1]=0
        for i in range(2,x+1):
            for j in range(i-1,x//i):
                k[i+j*i] = 0
        return k

    t = fur(10**6)

    cnt = 0

    def soi(x):
        global t,cnt
        for i in range(2,int(math.sqrt(x))+1):
            if x%i==0:
                if t[i] == 1:
                    t[i] = 2
                if t[x//i] == 1:
                    t[x//i] = 2
                if t[i] == 2 or t[x//i] == 2:
                    cnt = 1
                    break
    
    for i in range(n):
        if cnt == 1:
            break
        else:
            soi(a[i])
    
    if cnt == 1:
        print("setwise coprime")
    
    else:
        print("pairwise coprime")
Problem p02701 (python)

Fixed submission:
N = int(input())
l = []
for i in range(N):
    l.append(input())
k = sorted(l)
ans = 0
a = 0
for i in range(N):
    if k[i]!=a:
        ans+= 1
        a = k[i]
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
l = [input()]
for i in range(1,N):
    s = 0
    t = i
    a = input()
    while t-s > 1:
        if a <= l[int((s+t+1)/2)]:
            t = int((s+t+1)/2)
        else:
            s = int((s+t+1)/2)
    if l[s] != a:
        l.insert(t,a)
print(len(l))
Problem p02725 (python)

Fixed submission:
[K,N]= [int(x) for x in input().split()]

lists = [int(x) for x in input().split()]
lists.sort()
sor = []
for i in range(N-1):
    sor.append(lists[i+1]-lists[i])
sor.append(K-lists[N-1]+lists[0])
print(K-max(sor))

Buggy submission (verdict: Runtime Error):
K = int(input())
N = int(input())
lists = [int(x) for x in input().split()]
lists.sort()
sor = []
for i in range(N-1):
    sor.append(lists[i+1]-lists[i])
sor.append(K-lists[N-1]+lists[0])
print(K-max(sor))
Problem p02916 (python)

Fixed submission:
N = int(input())
A = input().split()
B = input().split()
C = input().split()

ans = 0
for i in range(N):
    ans+= int(B[i])

for i in range(N-1):
    if int(A[i])+1 ==int(A[i+1]):
        ans+=int(C[int(A[i])-1])

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = input().split()
B = input().split()
C = input().split()

ans = 0
for i in range(N):
    ans+= int(B[i])

for i in range(N-1):
    if int(A[i])+1 ==int(A[i+1]):
        ans+=int(C[int(A[i])])

print(ans)

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

ans = 0
for i in range(N):
    ans+= B[i]

for i in range(N-1):
    if A[i]+1 ==A[i+1]:
        ans+= C[A[i]]

print(ans)
Problem p02580 (python)

Fixed submission:
import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append(tuple([h-1, w-1]))
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    bombs = set(bombs)
    for i in maxhindex:
        for j in maxwindex:
            if (i, j) not in bombs:
                print(ans)
                exit()

    print(ans-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs = []
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append([h-1, w-1])
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    for i in maxindex:
        for j in maxwindex:
            if [i, j] not in bombs:
                print(ans)
                exit()

    print(ans-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline

def main():
    ans = 0
    H, W, M = map(int, input().split())
    bombs
    hs = [0]*(H)
    ws = [0]*(W)
    for _ in range(M):
        h, w = map(int, input().split())
        bombs.append([h-1, w-1])
        hs[h-1] += 1
        ws[w-1] += 1
    maxh = max(hs)
    maxw = max(ws)
    ans = maxh + maxw

    maxhindex = [i for i, x in enumerate(hs) if x == maxh]
    maxwindex = [i for i, x in enumerate(ws) if x == maxw]

    isfound = False

    # for i in maxindex:
    #     for j in maxwindex:
    #         if [i, j] not in bombs:
    #             print(ans)
    #             exit()

    # print(ans-1)

if __name__ == '__main__':
    main()
Problem p02623 (python)

Fixed submission:
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_cs, b_cs = [0], [0]
for i in range(n):
  a_cs.append(a_cs[i] + a[i])
for i in range(m):
  b_cs.append(b_cs[i] + b[i])

ans, j = 0, m
for i in range(n+1):
  if a_cs[i] > k:
    break
  while b_cs[j] > k - a_cs[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)

Buggy submission (verdict: Runtime Error):
n ,m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
while k > 0:
  i, j = 0
  if a[i] <= b[j]:
    k -= a[i]
    if k >= 0
      i += 1
      ans += 1
      if i >= n:
        for o in range(j, m):
          if k >= b[o]:
            k -= b[o]
            ans += 1
          else:
            k -= b[o]
            break
  else:
    k -= b[j]
    if k >= 0
      j += 1
      ans += 1
      if j >= m:
        for p in range(i, n):
          if k >= a[p]:
            k -= a[p]
            ans += 1
          else:
            k -= a[p]
            break
print(ans)

Buggy submission (verdict: Runtime Error):
n ,m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0
while k > 0:
  i, j = 0
  if a[i] <= b[j]:
    k -= a[i]
    if k >= 0
      i += 1
      ans += 1
  else:
    k -= b[j]
    if k >= 0
      j += 1
      ans += 1
print(ans)
Problem p02629 (python)

Fixed submission:
n = int(input())
ans = ''
while n > 0:
  n -= 1
  ans += chr(ord('a')+n%26)
  n //= 26
print(ans[::-1])

Buggy submission (verdict: Runtime Error):
n = int(input())
ans = ''
while n > 0:
  n -= 1
  ans += chr(ord('a')+ans%26)
  n //= 26
print(ans[::-1])
Problem p02688 (python)

Fixed submission:
def main():
    ans = 0
    n,k = map(int, input().split())
    l = [0]*n
    for i in range(k):
        d = int(input())
        s = list(map(int, input().split()))
        for j in s:
            l[j-1] += 1
    for i in range(n):
        if l[i] == 0:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    ans = 0
    n,k = map(int, input(.split()))
    l = [0]*n
    for i in range(k):
        d = int(input())
        s = list(map(int, input().split()))
        for j in s:
            l[j-1] += 1
    for i in range(n):
        if l[i] == 0:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
3 3
1
3
1
3
1
3
Problem p02725 (python)

Fixed submission:
k,n = map(int, input().split())
l = list(map(int, input().split()))
d = []
for i in range(n):
  if i + 1 < n:
    d.append(l[i+1]-l[i])
  else:
    if 0 in l:
      d.append(k - l[i])
    else:
      d.append(k - l[i] + l[0])
sum = sum(d)
a = []
for i in range(n):
  a.append(sum - d[i])
print(min(a))

Buggy submission (verdict: Runtime Error):
k, n = map(int, input().split())
l = list(map(int, input().split()))
d = []
for i in range(n):
  if i+1<n:
    d.append(abs(l[i+1]-l[i]))
  else:
    if 0 in l:
      d.append(abs(k - l[i]))
    else:
      d.append(abs(k - l[i] + l[0])
print(sum(d)-max(d))
Problem p02754 (python)

Fixed submission:
n,b,r = map(int, input().split())
s = n // (b+r)
a = n % (b+r)
ans = s * b
ans += min(a, b)
print("{}".format(ans))

Buggy submission (verdict: Runtime Error):
n,b,r = map(int, input().split())
s = n // (b+r)
a = n % (b+r)
ans = s * b
ans += min(a, b)
print({}.format(ans))
Problem p03127 (python)

Fixed submission:
import fractions
from functools import reduce
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
n = int(input())
l = list(map(int, input().split()))
print(gcd_list(l))

Buggy submission (verdict: Runtime Error):
import fraction
from functools import reduce
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
n = int(input())
l = list(map(int, input().split()))
print(gcd_list(l))
Problem p03107 (python)

Fixed submission:
S = input()
z_cnt = 0
o_cnt = 0
for i in S:
    if i == '0':
        z_cnt += 1
    if i == '1':
        o_cnt += 1
print(len(S)-(max(z_cnt,o_cnt)-min(z_cnt,o_cnt)))

Buggy submission (verdict: Runtime Error):
n = int(input())
s = input()
cnt1 = 0
cnt2 = 0
for i in range(n):
    if s[i] == '0':
        cnt1 += 1
    else:
        cnt2 += 1
print(min(cnt1, cnt2)*2)
Problem p03108 (python)

Fixed submission:
N, M = map(int, input().split())
a_list = []
b_list = []
for i in range(M):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

par = [i for i in range(N+1)]
rank = [0]*(N+1)
size = [1] * (N + 1)

def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x_par = find(x)
    y_par = find(y)
    if x_par == y_par:
        return
    if rank[x_par] < rank[y_par]:
        par[x_par] = y_par
        size[y_par] += size[x_par]
    else:
        par[y_par] = x_par
        size[x_par] += size[y_par]
        if rank[x_par] == rank[y_par]:
            rank[x_par] += 1


def bool_func(x, y):
    if find(x) == find(y):
        return True
    else:
        return False


ans_list = []      
ans = int(N*(N-1)/2)
for i in range(M):
    ans_list.append(ans)
    a = a_list[M-1-i]
    b = b_list[M-1-i]
    p = size[find(a)]
    q = size[find(b)]
    if bool_func(a, b):
        pass
    else:
        ans -= p*q
        unite(a, b)

for i in range(M):
    print(ans_list[M-1-i])

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
a_list = []
b_list = []
for i in range(M):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N+1)]
        self.rank = [0]*(N+1)
        self.size = [1] * (N + 1)
    
    def find(self, x):
        if self.par[x] == x:
            return self.par[x]
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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


    def unite(self, x, y):
        x_par = self.find(x)
        y_par = self.find(y)
        if x_par == y_par:
            return
        if self.rank[x_par] < self.rank[y_par]:
            self.par[x_par] = y_par
            self.size[y_par] += self.size[x_par]
        else:
            self.par[y_par] = x_par
            self.size[x_par] += self.size[y_par]
            if self.rank[x_par] == self.rank[y_par]:
                self.rank[x_par] += 1


    def isunite(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


uf = UnionFind(N)
ans_list = []      
ans = int(N*(N-1)/2)
for i in range(M):
    ans_list.append(ans)
    a = a_list[M-1-i]
    b = b_list[M-1-i]
    if uf.isunite(a, b):
        pass
    else:
        p = uf.fsize(a)
        q = uf.fsize(b)
        ans -= p*q
        uf.unite(a, b)

for i in range(M):
Problem p02695 (python)

Fixed submission:
N,M,Q=map(int,input().split())
L = []
for i in range(Q):
  L.append(list(map(int, input().split())))
  L[i][0]-=1
  L[i][1]-=1

import itertools

l =list(range(1,M+1))
ans=0

v=list(itertools.combinations_with_replacement(l,N))

for arr in v:
  score=0
  for a,b,c,d in L:
    if (arr[b] - arr[a])==c:
      
      score+=d
  ans=max(ans,score)
print(ans)

Buggy submission (verdict: Runtime Error):
N,M,Q=map(int,input().split())
L=[]
for i in range(Q):
  L.append(list(map(int,input().split())))
  L[i][0]-=1
  L[i][1]-=1

import itertools
L=list(range(1,M+1))
A=list(itertools.combinations_with_replacement(L,N))
ans=0
for i in A:
  tmp=0
  for a,b,c,d in L:
    if (i[b]-i[a])==c:
      tmp+=d
  ans=max(ans,tmp)
print(ans)
Problem p02762 (python)

Fixed submission:
class UnionFind():
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1) #各iについて、iと同一の連結成分に属する友達関係の人、ブロック関係の人の数を数える
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 #各iについて、iと同一の連結成分に属する友達関係の人の数を数える
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 #各iについて、iと同一の連結成分に属するブロック関係の人の数を数える
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] #答えは(各iが属する連結成分のサイズ)-1-((iと同一の連結成分に含まれているiと友達関係にある人の数)+(iと同一の連結成分に含まれているiとブロック関係にある人の数)となる
print(*ans[1:])

Buggy submission (verdict: Runtime Error):
＃@YottyPG　Qiita
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])
Problem p02935 (python)

Fixed submission:
N=int(input())
L=list(map(int,input().split()))
LR=sorted(L)
ans=LR[0]
for i in range(N-1):
  ans=(ans+LR[i+1])/2
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
L=list(map(int,input().split()))
LR=sorted(L,reverse=True)
ans=0
for i range(N-1):
  ans=(L[i]+L[i+1])/2
print(ans)
Problem p02989 (python)

Fixed submission:
N=int(input())
D=list(map(int,input().split()))
D=sorted(D)
ans=D[N//2]-D[N//2-1]
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
D=list(map(int,input().split()))
DS=sorted(D)
ans=DS[N//2]-DS[D//2-1]
print(ans)
Problem p03013 (python)

Fixed submission:
n,m = map(int,input().split())
A = set([int(input()) for _ in range(m)])
mod = 1000000007
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2])%mod
    if i in A:dp[i] = 0
print(dp[n])

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[]
for i in range(M):
  A.append(int(input()))
ans=0
MOD=1000000007
dp=[]
for i in range(N-1,0,-1):
  if i in A:
    dp[i]=0
    continue
  dp[i]=dp[i+1]+dp[i+2]
  
ans=dp[0]
ans/=MOD
print(ans)
Problem p03077 (python)

Fixed submission:
N=int(input())
A=[int(input()) for i in range(5)]
X=min(A)
ans=(N+X-1)//X +4
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
ls = [int(input()) for range(5)]
X = min(ls)
print((N+X-1)//X+4)

Buggy submission (verdict: Runtime Error):
N=int(input())
A=[int(input()) for range(N)]
X=min(A)
ans=(N+X-1)//X +4
print(ans)
Problem p03222 (python)

Fixed submission:
'''3/18 AtCoder（漸化式dp）
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、
「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、
高さh-1からこの位置に至ることができるのは、
棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局
「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
ということである
つまり、この高さにおける横棒の架かり方というのは
「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる　
高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
j-1本の棒の間にかかる橋の場合の数f(j-1)と、
W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
これと同様に、残り二本に対してもいくつかければよいかを考えて、
dp[h][j]]に対する漸化式を立てればよい
'''
H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ（f(n)=f(n-1)+f(n-2)）
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ0は初期位置なので1に
if W != 1: #棒が一本以上あるときは
  for i in range(1,H+1):
    for j in range(W): #棒が左端、右端、それ以外で場合分け
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7)) #高さH（一番下）、K-1番目の棒を調べる

Buggy submission (verdict: Runtime Error):
'''Yoshichiの日記
あみだくじ。
0本目からスタートし、W本の長さH + 1までにを任意の線を引いた時
K本目にたどり着くパターンは何パターンあるか答えよ。
現在の位置状態での線の引き方を全列挙し、DP(メモ化再帰)を用いて答える。
x → 現在の位置
y → 現在の進み具合
for分のi → 現在の位置にいる時の線の配置状態(1が隣接へつながっているとき)
for分のj → NGパターンの列挙(隣へ繋がっているかつ、
                   次の隣へも線が引かれている状態)
'''
h, w, k = map(int, input().split())
memo = defaultdict(lambda:defaultdict(int))
def dfs(x, y):
    if y == h:
        if x == k - 1:
            return 1
        else:
            return 0
    if y in memo[x]:
        return memo[x][y]

    ans = 0
    for i in range(1 << w - 1):
        flg = True
        for j in range(w - 2):
            if i & (1 << j) and i & (1 << j + 1):
                flg = False
                break
        if flg:
            nx = x
            if x > 0 and i & (1 << x - 1):
                nx = x - 1
            elif i & (1 << x):
                nx = x + 1
            ans += dfs(nx, y + 1)
            ans %= 1000000000 + 7
    memo[x][y] = ans
    return ans
print(dfs(0, 0))
Problem p03242 (python)

Fixed submission:
n = input()
for c in n:
    if (c == '1'):
        print('9', end='')
    elif (c == '9'):
        print('1', end='')
    else:
        print(c, end='')
print()

Buggy submission (verdict: Runtime Error):
A=input()
for i in range(3):
  if A[i]=='1':
    A[i]='9'
  else if A[i]=='9':
    A[i]='1'
print('A')

Buggy submission (verdict: Runtime Error):
A=input()
for i in range(3):
  if A[i]=='1':
    A[i]='9'
  else if A[i]=='9':
    A[i]='1'
print(A)

Buggy submission (verdict: Runtime Error):
A=int(input().split())
for i in range(3):
  if A[i]==1:
    A[i]=9
  else if A[i]==9:
    A[i]=1
print(A)
Problem p03250 (python)

Fixed submission:
A,B,C=sorted(map(int,input().split()))
print(10*C+A+B)

Buggy submission (verdict: Runtime Error):
A,B,C=(map(int,input().split())).sort()
print(10*C+B+A)
Problem p03307 (python)

Fixed submission:
N=int(input())
if N%2==0:
  ans=N
else:
  ans=2*N
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
if N%2==0:
  ans=N
else:
  ans=2N
print(ans)
Problem p03803 (python)

Fixed submission:
A,B=map(int,input().split())
if A==B:
  print('Draw')
elif A==1:
  print('Alice')
elif B==1:
  print('Bob')
elif A>B:
  print('Alice')
else:
  print('Bob')

Buggy submission (verdict: Runtime Error):
A,B=map(int,input().split())
if A==B:
  print('Draw')
else if A=='1':
  print('Alice')
else if B=='1':
  print('Bob')
else if A>B:
  print('Alice')
else:
  print('Bob')