Problem p03013 (python)

Fixed submission:
if __name__ == '__main__':
   n, m = map(int,input().split())
   a = set([int(input()) for i in range(m)])

   MOD = 1000000007

   dp = [0 for i in range(n+1)]
   dp[0] = 1
   if 1 in a:
      dp[1] = 0
   else:
      dp[1] = 1

   for i in range(2,n+1):
      if (i-1 in a) and (i-2 in a):
         dp[i] = 0
      elif i-1 in a:
         dp[i] = dp[i-2] % MOD
      elif i-2 in a:
         dp[i] = dp[i-1] % MOD
      else:
         dp[i] = (dp[i-1] + dp[i-2]) % MOD

   print(dp[n])

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007


def step_state(n, broken):
    if n == 0:
        return 1
    elif n == 1:
        if broken[1]:
            return 0
        else:
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            return 0
        elif broken[n - 1]:
            return step_state(n-2, broken) % MOD
        elif broken[n-2]:
            return step_state(n-1, broken) % MOD
        else:
            return (step_state(n-1, broken)+step_state(n-2, broken)) % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007

state = [-1 for i in range(100010)]

def step_state(n, broken):
    if state[n] != -1:
        return state[n]

    if n == 0:
        state[0]=1
        return 1
    elif n == 1:
        if broken[1]:
            state[1]=0
            return 0
        else:
            state[1]=1
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            state[n]=0
            return 0
        elif broken[n - 1]:
            state[n]=step_state(n-2, broken) % MOD
            return state[n]
        elif broken[n-2]:
            state[n] = step_state(n-1, broken) % MOD
            return state[n]
        else:
            state[n] = (step_state(n-1, broken)+step_state(n-2, broken)) % MOD
            return state[n]


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

MOD = 1000000007


def step_state(n, broken):
    if n == 0:
        return 1
    elif n == 1:
        if broken[1]:
            return 0
        else:
            return 1
    else:
        if broken[n - 1] and broken[n - 2]:
            return 0
        elif broken[n - 1]:
            return step_state(n-2, broken) % MOD
        elif broken[n-2]:
            return step_state(n-1, broken) % MOD
        else:
            return (step_state(n-1, broken)+step_state(n-2, broken)) % MOD


if __name__ == '__main__':
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])
    broken = [False] * (n+1)
    for i in range(n+1):
        if i in a:
            broken[i] = True

    answer = step_state(n, broken)

    print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_set, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_set:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_set, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_set, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N*2)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        answer = calc_state_number(N, 0, set(a), memo)

    print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N*2)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)

    print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(100000)

def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        return 0
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N+2)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)

    print(answer)

Buggy submission (verdict: Runtime Error):
def calc_state_number(stair_num, now_stair, damaged_step_list, memo):
    # print(str(now_stair) + '/' + str(stair_num))
    if memo[now_stair-1] != -1:
        return memo[now_stair-1]
    if now_stair in damaged_step_list:
        memo[now_stair-1] = 0
        return memo[now_stair-1]
    if now_stair > stair_num:
        return 0
    if now_stair == stair_num:
        memo[now_stair-1] = 1
        return memo[now_stair-1]
    memo[now_stair-1] = (calc_state_number(stair_num, now_stair+1, damaged_step_list, memo) + calc_state_number(stair_num, now_stair+2, damaged_step_list, memo))%1000000007
    return memo[now_stair-1]

if __name__ == '__main__':
    N, M = map(int, input().split())
    a = [int(input()) for _ in range(M)]
    a = sorted(a)

    memo = [-1] * (N+2)

    answer = 1
    if a[-1::] == N:
        answer = 0

    for i in range(1, M):
        if a[i-1] + 1 == a[i]:
            answer = 0

    if answer != 0:
        answer = calc_state_number(N, 0, a, memo)
    
    print(answer)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(1000000)

MAX_N = 100010
memo = [-1] * MAX_N

def f(n, na_set):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        if len(na_set & set([1])) == 1:
            return 1
        return 2
    # すでに探索済みならメモを参照する
    elif memo[n] != -1:
        return memo[n]
    else:
        is_next_damaged = False
        is_2next_damaged = False

        if len(na_set & set([n-1])) == 1:
            is_next_damaged = True
        if len(na_set & set([n-2])) == 1:
            is_2next_damaged = True
        if is_next_damaged == True and is_2next_damaged == False:
            res = f(n-2, a_list)
        if is_next_damaged == False and is_2next_damaged == True:
            res = f(n-1, a_list)
        if is_next_damaged == False and is_2next_damaged == False:
            res = f(n-1, a_list) + f(n-2, a_list)

    # メモ
    memo[n] = res
    return res

if __name__ == '__main__':
    N, M = map(int, input().split())
    a_list = [int(input()) for i in range(M)]
    na_set = set([N-a for a in a_list])
    
    divided_by = 1000000007

    answer = -1

    # まず移動方法がない場合を考える。
    min_diff = sys.maxsize
    for i in range(1, len(a_list)):
        min_diff = min(min_diff, a_list[i] - a_list[i - 1])

    if min_diff == 1:
        answer = 0
    else:
        # 何らかなの移動方法が必ず存在する場合
        answer = f(N, na_set)%divided_by

    print(answer)