Problem p03013 (python)

Fixed submission:
n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
dp = [0]*(n+2)
for i in a:
    dp[i] = -1
dp[0] = 1

for i in range(n):
    if dp[i]<0:
        continue
    dp[i] %= 10**9+7
    if dp[i+1]>=0:
        dp[i+1] += dp[i]
    if dp[i+2]>=0:
        dp[i+2] += dp[i]
print(dp[n]%(10**9+7))

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

import sys
sys.setrecursionlimit(100000) 

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

@lru_cache(maxsize=100000)
def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
        return memo[k]

print(stair(n))

Buggy submission (verdict: Runtime Error):
from functools import lru_cache
@lru_cache(maxsize=100000)

import sys
sys.setrecursionlimit(100000) 

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
        return memo[k]

print(stair(n))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000) 

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

for i in a:
    memo[i] = 0

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + memo[1]
            else:
                memo[k] = 0 + memo[1]
        elif k not in a:
            if k-1 not in a or k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
        return memo[k]

print(stair(n))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000) 

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

for i in a:
    memo[i] = 0

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a or k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
            else:
                memo[k] = 0
        else:
            memo[k] = 0
        return memo[k]

print(stair(n))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000) 

n,m = list(map(int,input().split()))
a = [0]*m
for i in range(m):
    a[i] = int(input())
memo = [-1]*(n+1)

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
    return memo[k]

print(stair(n))

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

def stair(k):
    if memo[k] != -1:
        return memo[k]
    else:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
    return memo[k]

print(stair(n))

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

def stair(k):
    if memo[k] == -1:
        if k == 1:
            if 1 not in a:
                memo[k] = 1
            else:
                memo[k] = 0
        elif k == 2:
            if 2 not in a:
                memo[k] = 1 + stair(1)
            else:
                memo[k] = 0 + stair(1)
        elif k not in a:
            if k-1 not in a:
                if k-2 not in a:
                    memo[k] = (stair(k-1)+stair(k-2))%1000000007
                else:
                    memo[k] = stair(k-1)
            else:
                if k-2 not in a:
                    memo[k] = stair(k-2)
                else:
                    memo[k] = 0
        else:
            memo[k] = 0
    return memo[k]

print(stair(n))

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

def stair(k):
    if k == 1:
        if 1 not in a:
            return 1
        else:
            return 0
    elif k == 2:
        if 2 not in a:
            return 1 + stair(1)
        else:
            return 0 + stair(1)
    if k not in a:
        if k-1 not in a:
            if k-2 not in a:
                return (stair(k-1)+stair(k-2))%1000000007
            else:
                return stair(k-1)
        else:
            if k-2 not in a:
                return stair(k-2)
            else:
                return 0
    else:
        return 0

print(stair(n))