Problem:


パスタ (Pasta)  

  問題

あなたはパスタが大好物であり，毎日，晩御飯にパスタを作って食べている．あなたはトマトソース，クリームソース，バジルソースの 3 種類のパスタを作ることができる．

N 日間の晩御飯の予定を考えることにした．それぞれの日に 3 種類のパスタから 1 種類を選ぶ．ただし，同じパスタが続くと飽きてしまうので，3 日以上連続して同じパスタを選んではいけない．また，N 日のうちの K 日分のパスタはすでに決めてある．

入力として N の値と，K 日分のパスタの情報が与えられたとき，条件をみたす予定が何通りあるかを 10000 で割った余りを求めるプログラムを作成せよ．

  入力

入力は K + 1 行からなる．

1 行目には 2 つの整数 N, K (3 ≦ N ≦ 100，1 ≦ K ≦ N) が空白を区切りとして書かれている．

1 + i 行目 (1 ≦ i ≦ K) には 2 つの整数 Ai, Bi (1 ≦ Ai ≦ N，1 ≦ Bi ≦ 3) が空白を区切りとして書かれている．これは，Ai 日目のパスタはすでに決まっており，Bi = 1 のときはトマトソースであり，Bi = 2 のときはクリームソースであり，Bi = 3 のときはバジルソースであることを表す．Ai (1 ≦ i ≦ K) は全て異なる．与えられる入力データにおいて，条件をみたす予定は 1 通り以上あることが保証されている．

  出力

条件をみたす予定が何通りあるかを 10000 で割った余りを 1 行で出力せよ．

  入出力例

入力例 1

  

5 3
3 1
1 1
4 2

出力例 1

   

6

入出力例 1 において，あなたは 5 日間の予定を考える．1 日目と 3 日目はトマトソースであり，4 日目はクリームソースである．また，3 日以上連続して同じパスタを選んではいけない．これらの条件をみたす予定は 6 通りある．

 

  
   1日目 
   2日目 
   3日目 
   4日目 
   5日目 
 

 

  予定 1   
  1
  2
  1
  2
  1
 

 

  予定 2   
  1
  2
  1
  2
  2
 

 

  予定 3   
  1
  2
  1
  2
  3
 

 

  予定 4   
  1
  3
  1
  2
  1
 

 

  予定 5   
  1
  3
  1
  2
  2
 

 

  予定 6   
  1
  3
  1
  2
  3
 

この表では，1 はトマトソースを，2 はクリームソースを，3 はバジルソースを表す．

入力例 2
  

  

20 5
10 2
4 3
12 1
13 2
9 1

出力例 2

   

2640

入出力例 2 において，条件をみたす予定は全部で 4112640 通りある．それを 10000 で割った余りである 2640 を出力する．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 3
3 1
1 1
4 2


Sample output:
6

Submission status: Wrong Answer

Solution code:
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()
#f.close()
import sys
N, K = [int(x) for x in sys.stdin.readline().split(' ')]
lines = sys.stdin.readlines()


schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [0]*9
for i in range(9):
    l1 = i // 3
    l2 = i % 3
    if(schedule[0]!=l1+1 and schedule[0]!=0):
        number[i] = 0
    elif(schedule[1]!=l2+1 and schedule[1]!=0):
        number[i] = 0
    else:
        number[i] = 1


for s in schedule[2:]:
    new_number = [0]*9
    for i in range(9):
        l1 = i // 3
        l2 = i % 3
        for j in range(3):
            new_number[i] += number[l2*3 + j] if((s==0 or s==l1+1) and  not (l2==j and l1==j)) else 0
    for i in range(9):
        number[i] = new_number[i] % 10000
      
sum = 0
for n in number:
    sum += n
print(sum % 10000)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
print(S)
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[~-st*3+~-nd]=1
 else:dp[~-st*3:st*3]=[1]*3
elif nd:dp[~-st::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur:
  cur-=1
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10**5)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
print(S)
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[~-st*3+~-nd]=1
 else:dp[~-st*3:st*3]=[1]*3
elif nd:dp[~-st::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur:
  cur-=1
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[~-st*3+~-nd]=1
 else:dp[~-st*3:st*3]=[1]*3
elif nd:dp[~-st::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i]-1;tmp=[0]*9
 if cur>0:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
dp=[0]*9
st,nd=S[:2];st-=1
if st:
 if nd:dp[st*3+~-nd]=1
 else:dp[st*3:st*3]=[1]*3
elif nd:dp[~-nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i]-1;tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b-1
dp=[0]*9
st,nd=S[:2]
if st+1:
 if nd+1:dp[st*3+nd]=1
 else:dp[st*3:st*3]=[1]*3
elif nd+1:dp[nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b-1
dp=[0]*9
st,nd=S[:2]
if st+1:
 if nd+1:dp[st*3+nd]=1
 else:dp[st*3:st*3]=[1]*3
elif nd+1:dp[nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur+1)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur+1)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b-1
dp=[0]*9
st,nd=S[:2]
if st+1:
 if nd+1:dp[st*3+nd]=1
 else:dp[st*3:-~st*3]=[1]*3
elif nd+1:dp[nd::3]=[1]*3
else:dp=[1]*9
print(dp)
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
rules = [map(int, input().split()) for _ in range(k)]

ans = [[0,1,1,1,1,1,1] for _ in range(n+1)]

dic = [0, [0,1,0,0,1,0,0], [0,0,1,0,0,1,0], [0,0,0,1,0,0,1]]
for [d, p] in rules:
    ans[d] = list(dic[p])

ans[1][4] = 0
ans[1][5] = 0
ans[1][6] = 0

for d in range(2, n+1):
    ans[d][1] = ans[d][1] * (ans[d-1][2] + ans[d-1][3] + ans[d-1][5] + ans[d-1][6])
    ans[d][2] = ans[d][2] * (ans[d-1][1] + ans[d-1][3] + ans[d-1][4] + ans[d-1][6])
    ans[d][3] = ans[d][3] * (ans[d-1][1] + ans[d-1][2] + ans[d-1][4] + ans[d-1][5])
    ans[d][4] = ans[d][4] *  ans[d-1][1]
    ans[d][5] = ans[d][5] *  ans[d-1][2]
    ans[d][6] = ans[d][6] *  ans[d-1][3]

print(sum(ans[n]) % 10000)

Submission status: Accepted

Solution code:
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()
#f.close()
import sys
N, K = [int(x) for x in sys.stdin.readline().split(' ')]
lines = sys.stdin.readlines()


schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [0]*9
for i in range(9):
    l1 = i // 3
    l2 = i % 3
    if(schedule[0]!=l2+1 and schedule[0]!=0):
        number[i] = 0
    elif(schedule[1]!=l1+1 and schedule[1]!=0):
        number[i] = 0
    else:
        number[i] = 1


for s in schedule[2:]:
    new_number = [0]*9
    for i in range(9):
        l1 = i // 3
        l2 = i % 3
        for j in range(3):
            new_number[i] += number[l2*3 + j] if((s==0 or s==l1+1) and  not (l2==j and l1==j)) else 0
    for i in range(9):
        number[i] = new_number[i] % 10000
sum = 0
for n in number:
    sum += n
print(sum % 10000)

Submission status: Accepted

Solution code:
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()
#f.close()
from sys import stdin
N, K = [int(x) for x in stdin.readline().split(' ')]
lines = stdin.readlines()

schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [1]*9
for i in range(9):
    l1 = i // 3
    l2 = i % 3
    if   schedule[0]!=l2+1 and schedule[0]!=0:
        number[i] = 0
    elif schedule[1]!=l1+1 and schedule[1]!=0:
        number[i] = 0

for s in schedule[2:]:
    tmp = [0]*9
    for i in range(9):
        l1 = i // 3
        l2 = i % 3
       	tmp[i] = [number[l2*3+j] for j in range(3) \
         if (s==0 or s==l1+1) and  not (l2==j and l1==j)]
    for i in range(9):
         number[i] = sum(tmp[i])
print(sum(number) % 10000)

Submission status: Accepted

Solution code:
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()
#f.close()
from sys import stdin
N, K = [int(x) for x in stdin.readline().split(' ')]
lines = stdin.readlines()

schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [1]*9
for i in range(9):
    (l1,l2) = divmod(i,3)
    if   schedule[0]!=l2+1 and schedule[0]!=0:
        number[i] = 0
    elif schedule[1]!=l1+1 and schedule[1]!=0:
        number[i] = 0

for s in schedule[2:]:
    tmp = [0]*9
    for i in range(9):
        (l1,l2) = divmod(i,3)
       	tmp[i] = [number[l2*3+j] for j in range(3) \
                 if (s==0 or s==l1+1) and  not (l2==j and l1==j)]
    number = [sum(tmp_i) for tmp_i in tmp]
print(sum(number) % 10000)

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
d = {}
for i in range(k):
    a, b = map(int, raw_input().split())
    d[a] = b
dp =[[[[0]*(n+1) for i in range(4)] for j in range(4)] for k in range(4)]
def solve(a, b, c, i):
    if dp[a][b][c][i]: return dp[a][b][c][i]
    if a == b and b == c: return 0
    if i in d and d[i] != 0 and d[i] != c: return 0
    if i > n: return 0
    if i == n: return 1
    dp[a][b][c][i] = (solve(b,c,1,i+1) + solve(b,c,2,i+1) + solve(b,c,3,i+1)) % 10000
    return dp[a][b][c][i]
ans = (solve(0,0,1,1) + solve(0,0,2,1) + solve(0,0,3,1)) % 10000
print ans

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
d = {}
for i in range(k):
    a, b = map(int, raw_input().split())
    d[a] = b
dp =[[[[0]*(n+1) for i in range(4)] for j in range(4)] for k in range(4)]
def solve(a, b, c, i):
    if dp[a][b][c][i]: return dp[a][b][c][i]
    if a == b == c: return 0
    if i in d and d[i] != c: return 0
    if i == n: return 1
    dp[a][b][c][i] = (solve(b,c,1,i+1) + solve(b,c,2,i+1) + solve(b,c,3,i+1)) % 10000
    return dp[a][b][c][i]
ans = (solve(0,0,1,1) + solve(0,0,2,1) + solve(0,0,3,1)) % 10000
print ans

Submission status: Accepted

Solution code:
N,K = map(int, raw_input().split())
P = [-1]*N
for _ in range(K):
    A,B = map(int, raw_input().split())
    P[A-1] = B-1
T = [[[0]*3 for i in range(3)] for j in range(N)]
for i in range(3):
    if P[0]==-1 or P[0]==i:
        for j in range(3):
            if P[1]==-1 or P[1]==j:
                T[1][i][j] = 1
for i in range(2, N):
    for j in range(3):
        if P[i]==-1 or P[i]==j:
            for k in range(3):
                for l in range(3):
                    if k!=j or l!=j:
                        T[i][k][j] += T[i-1][l][k]
                        T[i][k][j] %= 10000
#print T
print sum(sum(t) for t in T[N-1])%10000

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
dic = [0 for i in range(n + 1)]
for i in range(k):
  a, b = map(int,input().split())
  dic[a] = b

dp = [[0] * 3 for i in range(3)]
temp = [[0] * 3 for i in range(3)]
first = dic[1]
second = dic[2]

if not first and not second:
  for i in range(3):
    for j in range(3):
      dp[i][j] = 1

elif not first:
  for i in range(3):
    dp[i][second - 1] = 1

elif not second:
  for i in range(3):
    dp[first - 1][i] = 1

else:
  dp[first - 1][second - 1] = 1

for i in range(3, n + 1):
  past = dic[i]
  if not past:
    for y in range(3):
      for x in range(3):
        temp[x][y] = sum(dp[j][x] for j in range(3) if not (x == y and x == j))
  else:
    for y in range(3):
      for x in range(3):
        if y == past - 1:
          temp[x][y] = sum(dp[j][x] for j in range(3) if not (x == y and x == j))
        else:
          temp[x][y] = 0
  
  for x in range(3):
    for y in range(3):
      dp[x][y] = temp[x][y]
print(sum([dp[i][j] for i in range(3) for j in range(3)]) % 10000)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[~-st*3+~-nd]=1
 else:dp[~-st*3:~-st*3]=[1]*3
elif nd:dp[~-nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i]-1;tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
dp=[0]*9
st,nd=S[:2];st-=1
if st+1:
 if nd:dp[st*3+~-nd]=1
 else:dp[st*3:st*3]=[1]*3
elif nd:dp[~-nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i]-1;tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:a,b=map(int,input().split());S[a-1]=b
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[~-st*3+~-nd]=1
 else:dp[~-st*3:st*3]=[1]*3
elif nd:dp[~-nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i]-1;tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=[-1]*N
for _ in[0]*K:a,b=map(int,input().split());S[a-1]=b-1
dp=[0]*9
st,nd=S[:2]
if st+1:
 if nd+1:dp[st*3+nd]=1
 else:dp[st*3:st*4]=[1]*3
elif nd+1:dp[nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:a,b=map(int,input().split());S[a-1]=b
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[st*2+~-nd]=1
 else:dp[st*2:st*3]=[1]*3
elif nd:dp[~-nd::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i]-1;tmp=[0]*9
 if cur+1:
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())


decided = {}

for x in xrange(k):
    a, b = map(int, raw_input().split())
    decided[a - 1] = b - 1

cnt = [[0] * 3 for x in xrange(n)]
dup = [[0] * 3 for x in xrange(n)]

if 0 in decided:
    cnt[0][decided[0]] = 1
else:
    for i in xrange(3):
        cnt[0][i] = 1

for x in xrange(1, n):
    if x in decided:
        i = decided[x]
        for j in xrange(3):
            if i == j:
                cnt[x][i] += cnt[x - 1][j] - dup[x - 1][j]
                dup[x][i] += cnt[x - 1][j] - dup[x - 1][j]
            else:
                cnt[x][i] += cnt[x - 1][j]
    else:
        for i in xrange(3):
            for j in xrange(3):
                if i == j:
                    cnt[x][j] += cnt[x - 1][j] - dup[x - 1][j]
                    dup[x][j] += cnt[x - 1][j] - dup[x - 1][j]
                else:
                    cnt[x][i] += cnt[x - 1][j]

ans = cnt[n - 1][0] + cnt[n - 1][1] + cnt[n - 1][2]
ans %= 10000

print ans

Submission status: Accepted

Solution code:
n,k = map(int,input().split())

table = [[0]*n for i in range(3)]

for _ in range(k):
	x,y=map(int,input().split())
	for i in range(3):
		table[i][x-1] = 0 if i == y-1 else -1

for i in range(3):
	if table[i][0] != -1:
		table[i][0] = 1

for i in range(1,n):
	s = 0
	for j in range(3):
		s += table[j][i-1] if table[j][i-1] != -1 else 0

	for j in range(3):
		if table[j][i] == -1:
			continue

		table[j][i] = s%10000

		if table[j][i-1] != -1 and table[j][i-2] != -1:
			if i == 1:
				continue
			table[j][i-1] -= table[j][i-2]
			table[j][i] -= table[j][i-2]

total = 0
for i in range(3):
	total += table[i][n-1] if table[i][n-1] != -1 else 0
total = total % 10000
print(total)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
#MOD = 1000000007
MOD = 10000
EPS = 0.000000001
sys.setrecursionlimit(100000)


tomato = 0
cream = 1
basil = 2
tomato_2 = 3
cream_2 = 4
basil_2 = 5

N,K = map(int,input().split())
dp = [[0]*6 for _ in range(N)]
decided = [-1]*N

#決まってる日
for _ in range(K):
    A,B = map(int,input().split())
    decided[A-1] = B-1

#初日
if decided[0] == -1:
    for i in range(3):
        dp[0][i] = 1
else:
    dp[0][decided[0]] = 1

for i in range(1,N):

    if decided[i] == -1:   #メニューが決まってない
        for pre in range(6):
            for tommorow in range(6):
                if pre%3 != tommorow%3: #別の種類
                    if tommorow >= 3: #2日連続ではない
                        continue
                    dp[i][tommorow] += dp[i-1][pre]
                    dp[i][tommorow] %= MOD
                else: #同じ種類
                    if pre < 3 and tommorow >= 3:
                        dp[i][tommorow] += dp[i-1][pre]
                        dp[i][tommorow] %= MOD
    else: #メニューが決まっている
        for pre in range(6):
            if pre%3 != decided[i]%3: #別種
                dp[i][decided[i]] += dp[i-1][pre]
                dp[i][decided[i]] %= MOD
            else: #同種
                if pre >= 3:
                    continue
                dp[i][decided[i]+3] += dp[i-1][pre]
                dp[i][decided[i]+3] %= MOD


ans = 0
for i in range(6):
    ans += dp[N-1][i]
    ans %= MOD

print("%d"%(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Pasta
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568

"""
import sys
from collections import Counter

def solve(n, decided):
    status = Counter({(0, 0, 0): 1})
    for d in range(1, n+1):
        u = Counter()
        pastas = range(1, 4)
        if decided and decided[-1][0] == d:
            pastas = [decided.pop()[1]]
        for k, v in status.items():
            _, d2, d3 = k
            for p in pastas:
                if not d2 == d3 == p:
                    u[(d2, d3, p)] += v
        status = Counter({k: v % 10000 for k, v in u.items()})
    return sum(status.values()) % 10000


def main(args):
    n, k = map(int, input().split())
    decided = sorted([list(map(int, input().split())) for _ in range(k)], reverse=True)
    ans = solve(n, decided)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def main(dp, n, menue):
  if menue == 0: m1, m2 = 1, 2
  elif menue == 1: m1, m2 = 0, 2
  elif menue == 2: m1, m2 = 0, 1
  dp[n][menue][0] += sum(dp[n-1][m1]) + sum(dp[n-1][m2])
  dp[n][menue][1] += dp[n-1][menue][0]

def run():
  N, K = map(int, input().split())
  dp = [[[0]*2 for _ in range(3)] for n in range(N)]
  k_li = [list(map(int, input().split())) for k in range(K)]
  k_li = sorted(k_li)
  #print(k_li)
  k_i = 0
  ka, kb = k_li[0]
  if ka == 1:
    dp[0][kb-1][0] = 1
    k_i += 1
    ka, kb = k_li[k_i]
  else:
    for k in range(3):
      dp[0][k][0] = 1
      
  for n in range(1, N):
    if (n+1) == ka:
      main(dp, n, kb-1)
      if k_i < K-1:
        k_i += 	1
        ka, kb = k_li[k_i]
    else:
      for menue in range(3):
        main(dp, n, menue)
  print(sum(map(sum, dp[-1]))%10000)
  #print(dp)
      
if __name__ == '__main__':
  run()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
dp=[[[0]*3 for j in range(2)] for i in range(N+1)]
#dp[i][j][k] iコメまででj+1回連続でkを食べる組み合わせ
G=[-1]*(N+1)
INF=10000
for i in range(K):
    a,b=map(int,input().split())
    b-=1
    G[a]=b
if G[1]!=-1:
    dp[1][0][G[1]]=1
else:
    dp[1][0][0]=dp[1][0][1]=dp[1][0][2]=1
for i in range(2,N+1):
    if G[i]!=-1:
        dp[i][0][G[i]]=(dp[i-1][0][(G[i]+1)%3]+dp[i-1][0][(G[i]+2)%3]+dp[i-1][1][(G[i]+1)%3]+dp[i-1][1][(G[i]+2)%3])%INF
        dp[i][1][(G[i])]=(dp[i-1][0][(G[i])])%INF
        continue
    for k in range(3):
        dp[i][0][k]=(dp[i-1][0][(k+1)%3]+dp[i-1][0][(k+2)%3]+dp[i-1][1][(k+1)%3]+dp[i-1][1][(k+2)%3])%INF
        dp[i][1][k]=(dp[i-1][0][k])%INF
ans=0
for j in range(2):
    for k in range(3):
        ans+=dp[N][j][k]
        ans%=INF
print(ans)

Submission status: Runtime Error

Solution code:
#f = open("input.txt")
#N, K = [int(x) for x in f.readline().split(' ')]
#lines = f.readlines()

import sys
N, K = [int(x) for x in sys.stdin.readline().split(' ')]
lines = sys.stdin.readlines()
f.close()

schedule = [0]*N
for line in lines:
    strs = line.split(' ')
    schedule[int(strs[0])-1] = int(strs[1])

number = [0]*9
for i in range(9):
    l1 = i // 3
    l2 = i % 3
    if(schedule[0]!=l1+1 and schedule[0]!=0):
        number[i] = 0
    elif(schedule[1]!=l2+1 and schedule[1]!=0):
        number[i] = 0
    else:
        number[i] = 1


for s in schedule[2:]:
    new_number = [0]*9
    for i in range(9):
        l1 = i // 3
        l2 = i % 3
        for j in range(3):
            new_number[i] += number[l2*3 + j] if((s==0 or s==l1+1) and  not (l2==j and l1==j)) else 0
    for i in range(9):
        number[i] = new_number[i] % 10000
      
sum = 0
for n in number:
    sum += n
print(sum % 10000)

Submission status: Runtime Error

Solution code:
n, k = map(int, raw_input().split())
d = {}
for i in range(k):
    a, b = map(int, raw_input().split())
    d[a] = b
dp =[[[[0]*(n+1) for i in range(4)] for j in range(4)] for k in range(4)]
def solve(a, b, c, i):
    if a == b == c: return 0
    if i in d and d[i] != c: return 0
    if i == n: return 1
    dp[a][b][c][i] = (solve(b,c,1,i+1) + solve(b,c,2,i+1) + solve(b,c,3,i+1)) % 10000
    return dp[a][b][c][i]
ans = (solve(0,0,1,1) + solve(0,0,2,1) + solve(0,0,3,1)) % 10000
print ans

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
S=[0]*N
for _ in[0]*K:
 a,b=map(int,input().split())
 S[a-1]=b
dp=[0]*9
st,nd=S[:2]
if st:
 if nd:dp[~-st*3+~-nd]=1
 else:dp[~-st*3:st*3]=[1]*3
elif nd:dp[~-st::3]=[1]*3
else:dp=[1]*9
for i in range(2,N):
 cur=S[i];tmp=[0]*9
 if cur:
  cur-=1
  for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 else:
  for cur in range(3):
   for k in range(3):tmp[k*3+cur]=sum(dp[k::3])-dp[cur*4]*(k==cur)
 dp=tmp[:]
print(sum(dp)%10000)