Problem p03013 (python)

Fixed submission:
import sys

n, m = list(map(int, input().split()))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

Buggy submission (verdict: Runtime Error):
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
import numpy as np


def fib(n):
    a = (1 + np.sqrt(5)) / 2
    b = (1 - np.sqrt(5)) / 2
    ans = (a**n - b**n) / np.sqrt(5)
    return int(ans)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    length = len(broken_stairs)
    if length == 0:
        print(fib(N) % 1000000007)
        sys.exit()

    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = fib(N - 2 * length)
        print(ans % 1000000007)

Buggy submission (verdict: Runtime Error):
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
sys.setrecursionlimit(100000)

dp = [-1] * 10005




CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = -1
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0] - 1)
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 2)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1] - 1)
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    print('holes', holes)
    for i in holes:
        if i == 0:
            i = 1
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    if M == 0:
        print(fib(N) % 1000000007)
        sys.exit()
    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(dp_list[:10])
        print(ans % 1000000007)

Buggy submission (verdict: Runtime Error):
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

import sys
sys.setrecursionlimit(100000)

dp = [-1] * 10005




CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = -1
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0] - 1)
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 2)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1] - 1)
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    print('holes', holes)
    for i in holes:
        if i == 0:
            i = 1
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    if M == 0:
        print(fib(N) / 1000000007)
        sys.exit()
    able = check_hole(M, broken_stairs)
    if not able:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(dp_list[:10])
        print(ans % 1000000007)

Buggy submission (verdict: Runtime Error):
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP
from sys import setrecursionlimit(1000000)


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)

Buggy submission (verdict: Runtime Error):
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 1 or n == 2:
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    broken_stairs = []
    for i in range(M):
        broken_stairs.append(int(input()))

    unable = check_hole(M, broken_stairs)
    if not unable:
        print(0)
    else:
        ans = find_ans(broken_stairs, N, M)
        print(ans % 1000000007)