Problem p03013 (python)

Fixed submission:
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N

    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if M==1:
        dp[0]=0
    else:
        dp[0]=1
    print(dp[N-1])
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
    else:
        dp[0] = 1
        dp[1] = 2
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if hoal[0]==1:
        dp[0]=0
    else:
        dp[0]=1
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
        
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2


if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2


if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

if 2 in hoal:
    dp[1] = 0
    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp)

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()
        
#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1

if M>=2:
    for i in range(N):
        if dp_check[i]==1 and dp_check[i+1]==1:
            print("0")
            exit()

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1

for i in range(N):
    if dp_check[i]==1 and dp_check[i+1]==1:
        print("0")
        exit()

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1 and dp_check[i]==0:
        dp[i]=dp[i-1]+dp[i-2]

    dp[i]=dp[i]%1000000007

print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1:
        dp[i]=dp[i-1]+dp[i-2]
    if i+1 in hoal:
        dp[i]=0
        if dp[i-1]==0:
            break
    dp[i]=dp[i]%1000000007

print(dp[N-1])

Buggy submission (verdict: Runtime Error):
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
if 1 in hoal:
    dp[0] = 0
    dp[1] = 1

#実際に求める
#dp[i]<-i段までの移動方法の和
for i in range(N):
    if i>1:
        dp[i]=dp[i-1]+dp[i-2]
    if i+1 in hoal:
        dp[i]=0
    dp[i]=dp[i]%1000000007

print(dp[N-1])