Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
Mod = 1000000007
dp = [1]*(N+1) #dp[i]...i番目にいる時の移動方法の数

count = 0
for i in range(1,N):
    if i in a:
        count += 1
        if count == 2:
            print(0)
            exit()
    else:
        count = 0

for i in range(N):
    if i in a:
        dp[i] = 0
if 1 in a:
    for i in range(1,N-1):
        if dp[i+2] != 0:
            dp[i+2] = dp[i+1] + dp[i]
            dp[i+2] %= Mod
else:
    dp[1] = 1
    for i in range(N-1):
        if dp[i+2] != 0:
            dp[i+2] = dp[i+1] + dp[i]
            dp[i+2] %= Mod

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
Mod = 1000000007
dp = [0]*(N+1) #dp[i]...i番目にいる時の移動方法の数
dp[0] = 1

count = 0
for i in range(1,N):
    if i in a:
        count += 1
        if count == 2:
            print(0)
            exit()
    else:
        count = 0
    
if 1 in a:
    dp[2] = 1
    for i in range(1,N-1):
        dp[i+2] = dp[i+1] + dp[i]
        dp[i+2] %= Mod
        if i+2 in a:
            dp[i+2] = 0
else:
    dp[1] = 1
    for i in range(N-1):
        dp[i+2] = dp[i+1] + dp[i]
        dp[i+2] %= Mod
        if i+2 in a:
            dp[i+2] = 0
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
Mod = 1000000007
dp = [0]*(N+1) #dp[i]...i番目にいる時の移動方法の数
dp[0] = 1

count = 0
for i in range(1,N):
    if i in a:
        count += 1
        if count == 2:
            print(0)
            exit()
    else:
        count = 0
    
if 1 in a:
    dp[2] = 1
    for i in range(1,N-1):
        dp[i+2] = dp[i+1] + dp[i]
        if i+2 in a:
            dp[i+2] = 0
else:
    dp[1] = 1
    for i in range(N-1):
        dp[i+2] = dp[i+1] + dp[i]
        if i+2 in a:
            dp[i+2] = 0
print(dp[N]%Mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = list(map(int, input().split()))
    A = []
    for i in range(M):
        A.append(int(input()))

    mod = 1000000007

    dp = [0] * (N+1)
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                #dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = list(map(int, input().split()))
    A = []
    for i in range(M):
        A.append(int(input()))

    mod = 1000000007

    dp = {i: 0 for i in range(N+1)}
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                #dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = list(map(int, input().split()))
    A = []
    for i in range(M):
        A.append(int(input()))

    mod = 1000000007

    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                #dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a - 1
        while left <= right:
            midle = floor(left + right)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle - 1
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a1_n = set([int(input()) for _ in range(m)])
P = 1000000007

pos_to_cnt = {
    0: 1
}
result = 0
while len(pos_to_cnt) > 0:
    new_pos_to_cnt = {}
    for p, c in pos_to_cnt.items():
        for steps in [1, 2]:
            new_pos = p + steps
            if new_pos <= n:
                new_pos_to_cnt[new_pos] = (new_pos_to_cnt.get(new_pos, 0) + c) % P
            else:
                break
    available_positions = set(new_pos_to_cnt.keys()) - a1_n
    pos_to_cnt = {pos: new_pos_to_cnt[pos] for pos in available_positions}
    result += pos_to_cnt.get(n, 0)

print(result % P)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a1_n = [int(input()) for _ in range(m)]
P = 1000000007

pos_to_cnt = {
    0: 1
}
result = 0
while len(pos_to_cnt) > 0:
    new_pos_to_cnt = {}
    for p, c in pos_to_cnt.items():
        for steps in [1, 2]:
            new_pos = p + steps
            if new_pos == n:
                result = (result + c) % P
                break
            elif new_pos < n and new_pos not in a1_n:
                new_pos_to_cnt[new_pos] = (new_pos_to_cnt.get(new_pos, 0) + c) % P
    pos_to_cnt = new_pos_to_cnt

print(result)

Submission status: Time Limit Exceeded

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

cnts = [1]
positions = [0]
result = 0
while len(positions) > 0:
    new_cnts = []
    new_positions = []
    for c, p in zip(cnts, positions):
        for steps in [1, 2]:
            new_pos = p + steps
            if new_pos == n:
                result = (result + c) % 1000000007
                break
            elif new_pos < n and new_pos not in a1_n:
                new_cnts.append(c)
                new_positions.append(new_pos)
    positions = list(set(new_positions))
    cnts = [sum([_c for _c, _p in zip(new_cnts, new_positions) if _p == pos]) % 1000000007 for pos in positions]

print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a1_n = set([int(input()) for _ in range(m)])

cnts = [1]
positions = [0]
result = 0
while len(positions) > 0:
    new_cnts = []
    new_positions = []
    for c, p in zip(cnts, positions):
        for steps in [1, 2]:
            new_pos = p + steps
            if new_pos == n:
                result += c
                break
            elif new_pos < n and new_pos not in a1_n:
                new_cnts.append(c)
                new_positions.append(new_pos)
    positions = list(set(new_positions))
    cnts = [sum([_c for _c, _p in zip(new_cnts, new_positions) if _p == pos]) for pos in positions]

print(result % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
List = [int(input()) for _ in range(M)]

P = 10**9+7
dp = [0]*(N+1)

dp[0] = 1
dp[1] = 1

for i in range(1, N):
    if i not in List:
        dp[i+1] = dp[i]+dp[i-1]
    else:
        dp[i] = 0
        dp[i+1] = dp[i-1]
            
print(dp[N]%P)

Submission status: Time Limit Exceeded

Solution code:
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    for i in range(stairs_num - 2):
        if i + 3 in broken_list:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
pat = [0]*(N+1)
for i in range(N+1):
  if i == 0:
    pat[i] = 1
  else:
    before1 = pat[i-1] if i-1 not in a else 0
    before2 = pat[i-2] if i-2 not in a else 0
    pat[i] = before1 + before2
print(pat[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    ans = [0] * (n + 1)
    ans[0] = ans[1] = 1
    for i in range(2, n + 1):
        if i in a:
            continue
        if i - 2 not in a:
            ans[i] += ans[i - 2]
        if i - 1 not in a:
            ans[i] += ans[i - 1]
    return str(ans[-1] % (10**9 + 7))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, M = map(int, input().split(" "))
	N += 1
	a = []
	for i in range(M):
		tmp = int(input())
		tmp += 1
		a.append(tmp)
		if i != 0 and tmp == a[-1]+1:
			print(0)
			sys.exit()
			
	DP = [0 for i in range(N)]
	for i in range(N):
		if i == 0:
			DP[0] = 1
			continue
		if N-i in a:
			continue
		tmp = 0
		if i == 1:
			DP[i] = DP[i-1] % 1000000007
		if i > 1:
			DP[i] = (DP[i-2] + DP[i-1]) % 1000000007
		
	#print(DP)
	print(DP[-1])
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, M = map(int, input().split(" "))
	N += 1
	a = []
	for i in range(M):
		tmp = int(input())
		tmp += 1
		a.append(tmp)
		if i != 0 and tmp == a[-1]+1:
			print(0)
			sys.exit()
			
	DP = [0 for i in range(N)]
	for i in range(N):
		if i == 0:
			DP[0] = 1
			continue
		if N-i in a:
			continue
		tmp = 0
		if i-1 >= 0:
			tmp = (tmp + (DP[i-1] % 1000000007)) % 1000000007
		if i-2 >= 0:
			tmp = (tmp + (DP[i-2] % 1000000007)) % 1000000007
		DP[i] = tmp
		
	#print(DP)
	print(DP[-1])
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():


    from collections import deque

    n, m = map(int, input().split())
    ddp = deque(maxlen=2)

    li_broken = [0] * m
    for i in range(m):
        li_broken[i] = int(input())

    ddp.appendleft(0)
    ddp.appendleft(1)

    li_i = list(reversed(range(n)))

    for i in li_i:

        if i in li_broken:
            ddp.appendleft(0)

        else:
            ddp.appendleft(sum(ddp) % 1000000007)

    print(ddp[0])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():


    from collections import deque

    n, m = map(int, input().split())
    ddp = deque(maxlen=2)

    li_broken = [0] * m
    for i in range(m):
        li_broken[i] = int(input())

    ddp.appendleft(0)
    ddp.appendleft(1)

    li_i = list(reversed(range(n)))

    for i in li_i:

        if i in li_broken:
            ddp.appendleft(0)

        else:
            ddp.appendleft(sum(ddp) % 1000000007)

    print(ddp[0])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():


    import sys
    input = sys.stdin.readline
    n, m = map(int, input().split())
    dp = [0] * (n + 2)

    li_broken = [0] * m
    for i in range(m):
        li_broken[i] = int(input())

    dp[n] = 1
    li_i = list(reversed(range(n)))

    for i in li_i:

        if i in li_broken:
            dp[i] = 0

        else:
            dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
dp = [0] * (n + 2)

li_broken = [0] * m
for i in range(m):
  li_broken[i] = int(input())

dp[n] = 1
li_i = list(reversed(range(n)))

for i in li_i:

  if i in li_broken:
    dp[i] = 0

  else:
    dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

      
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
def resolve():


    import sys
    input = sys.stdin.readline
    n, m = map(int, input().split())
    dp = [0] * (n + 2)

    li_broken = [0] * m
    for i in range(m):
        li_broken[i] = int(input())

    dp[n] = 1
    li_i = list(reversed(range(n)))

    for i in li_i:

        if i in li_broken:
            dp[i] = 0

        else:
            dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)
    
    dp[n] = 1

    for i in reversed(range(n)):

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)

    for i in reversed(range(n + 1)):

        if i == n:
            dp[i] = 1
            continue

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007

    print(dp[0])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)

    for i in reversed(range(n + 1)):

        if i == n:
            dp[i] = 1
            continue

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = dp[i+1] + dp[i+2]

    print(dp[0] % 1000000007)
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

lst = [0] * N
skips = [int(input()) for _ in range(M)]
for x in range(N):
    if x in skips:
        lst[x] = 0
    elif x in [0, 1]:
        lst[x] = 1
    else:
        lst[x] = (lst[x - 1] + lst[x - 2]) % 1000000007

if N == 1:
    print(lst[-1])
else:
    print((lst[-1] + lst[-2]) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

lst = [0] * N
skips = [int(input()) for _ in range(M)]
for x in range(N):
    if x in skips:
        lst[x] = 0
    elif x in [0, 1]:
        lst[x] = 1
    else:
        lst[x] = lst[x - 1] + lst[x - 2]

if N == 1:
    print(lst[-1] % 1000000007)
else:
    print((lst[-1] + lst[-2]) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#ABC129-C
N,M=map(int,input().split())
a=[]
num=0 #N段までの行き方
check=0 #行けるかどうか
for i in range(M):
    a.append(int(input()))

for i in range(M-1):
    dif=a[i+1]-a[i]
    if dif==1:
        check=1
        break
        
f={}
f[0]=0 #番号を段数と一致させるため
if (1 in a)==True: #１が壊れているとき
    f[1]=0
else:
    f[1]=1
if (2 in a)==True: #２が壊れているとき
    f[2]=0
elif f[1]==0: #１が壊れているとき
    f[2]=1
else:
    f[2]=2

if check==0:
    for i in range(1,N-1): #1~N-2
        if any(i+2==a[k] for k in range(M)): #壊れている階段は、２段前に見つけておく。
            f[i+2]=0
            continue
        f[i+2]=f[i+1]+f[i]
    num=f[N]

#for i in range(101):
    #print(str(i)+":"+str(f[i]))
print(num%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())

max_step = z[0] 
def steps(cand):
  tmp = []
  for j in range(len(cand)):
    tmp.append(sum(cand[:j+1]))
  return tmp

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

count = 0
all_count = 0

for i in range(int(max_step/2+0.5), max_step+1):
    #iは段の数
    #i = 5  1 = 0 ,2 = 5
    #i = 10 1 = 10, 2 = 0
    # 1 ... (i - 5) * 2  2 ... -1 * i + 10
    #1... (i - max_step/2)  2...-1 * i  + max_step
    num_1 =int( (i - max_step/2)*2)
    num_2 = (-1 * i + max_step)
    template_steps = []
    for j in range(num_1):
        template_steps.append(1)
    for j in range(num_2):
        template_steps.append(2)
    #print(template_steps)
    
    index = list(range(len(template_steps)))
    arrays = []
    for indexes in list(itertools.permutations(index)):
      arrays.append([template_steps[x] for x in indexes])
    #print(arrays)
#    arrays = get_unique_list(arrays)
    arrays = list(map(list, set(map(tuple, arrays))))
    
    for j in range(len(arrays)):
      all_count += 1
      for b in broken:
        if list(steps(arrays[j])).count(int(b)) > 0:
          #arrays[j] = [0,0]
          count += 1
          break  
print((all_count - count)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())

max_step = z[0] 
def steps(cand):
  tmp = []
  for j in range(len(cand)):
    tmp.append(sum(cand[:j+1]))
  return tmp

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

count = 0
all_count = 0

for i in range(int(max_step/2+0.5), max_step+1):
    #iは段の数
    #i = 5  1 = 0 ,2 = 5
    #i = 10 1 = 10, 2 = 0
    # 1 ... (i - 5) * 2  2 ... -1 * i + 10
    #1... (i - max_step/2)  2...-1 * i  + max_step
    num_1 =int( (i - max_step/2)*2)
    num_2 = (-1 * i + max_step)
    template_steps = []
    for j in range(num_1):
        template_steps.append(1)
    for j in range(num_2):
        template_steps.append(2)
    #print(template_steps)
    
    index = list(range(len(template_steps)))
    #print(index)
    arrays = []
    for indexes in list(itertools.permutations(index)):
      arrays.append([template_steps[x] for x in indexes])
    #print(arrays)
    arrays = get_unique_list(arrays)
    
    for j in range(len(arrays)):
      all_count += 1
      for b in broken:
        if list(steps(arrays[j])).count(int(b)) > 0:
          #arrays[j] = [0,0]
          count += 1
          break  
print((all_count - count)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
def steps(cand):
#  tmp = np.zeros_like(cand)
  tmp = []
  for j in range(len(cand)):
    tmp.append(sum(cand[:j+1]))
  return tmp

count = 0
all_count = 0
A = [1 , 2 ]

for i in range(int(max_step/2), max_step+1):
    #iは段の数
    
    for v in itertools.product(A, repeat = i):
      if sum(v) == max_step:
        all_count += 1
        for b in broken:
          if list(steps(v)).count(int(b)) > 0:
            count += 1
            break
        
print((all_count - count)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
def steps(cand):
#  tmp = np.zeros_like(cand)
  tmp = []
  for j in range(len(cand)):
    tmp.append(sum(cand[:j+1]))
  return tmp

count = 0
all_count = 0
A = [1 , 2 ]

for i in range(int(max_step/2), max_step+1):
    #iは段の数
    
    for v in itertools.product(A, repeat = i):
      if sum(v) == max_step:
        all_count += 1
        for b in broken:
          if list(steps(v)).count(int(b)) > 0:
            count += 1
            break
        

print((all_count - count)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    tmp[j] = sum(cand[:j+1])
  return tmp


count = 0
all_count = 0

for i in range(int(max_step/2), max_step+1):
    #iは段の数
        
    import itertools
    A = [1 , 2 ]
    for v in itertools.product(A, repeat = i):
      if sum(v) == max_step:
        all_count += 1
        for b in broken:
          if list(steps(v)).count(int(b)) > 0:
            count += 1
            break
        
#         all_possible.append(steps(v))
          
 

#for i in range(len(all_possible)):
  #all_possible[i] = steps(all_possible[i])
#  all_count += 1
 # for b in broken:
    #print( list(all_possible[i]).count(int(b)))
  #  if  list(all_possible[i]).count(int(b)) > 0:
    #    all_possible[i]= [0,0]
       # count += 1
        
print((all_count - count)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
z = input().split()
z = [ int(x) for x in z]
broken = []
for i in range(z[1]):
    broken.append(input())
#print(broken)

max_step = z[0] 
import numpy as np

all_possible = []

def steps(cand):
  tmp = np.zeros_like(cand)
  for j in range(len(cand)):
    tmp[j] = sum(cand[:j+1])
#    for i in range(len(cand[0])):
 #       tmp[j][i] = sum(cand[j][:i+1])
  return tmp

template_steps = []
for i in range(int(max_step/2), max_step+1):
    template_steps = []
    #iは段の数
        
    import itertools
    
    #for v in itertools.permutations(template_steps):
      #  arrays.append(v)
    A = [1 , 2 ]
    for v in itertools.product(A, repeat = i):
      if sum(v) == max_step:
         all_possible.append(v)

#print(all_possible)    
count = 0
all_count = 0

for i in range(len(all_possible)):
  #print(i)
  all_possible[i] = steps(all_possible[i])
  #print(list(all_possible[i]).count(2))
  
  all_count += 1
    
  for b in broken:
    #print( list(all_possible[i]).count(int(b)))
    if  list(all_possible[i]).count(int(b)) > 0:
        all_possible[i]= [0,0]
        count += 1
        
print((all_count - count)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
if n % 2 == 0:
    nn = n / 2
else:
    nn = (n - 1) / 2
nn = int(nn)
count = 0
for k in range(nn + 1):   #nじゃない
    searchlist = np.zeros(n)
    for i in range(n - 2*k):
        searchlist[i] = 1
    for i in range(k):
        searchlist[i + (n - 2*k)] = 2
    searchlist = searchlist.tolist()
    searchlist = [i for i in searchlist if i > 0]
    searchseed = len(searchlist)
    if searchseed == n:
        searcher = [1]
    elif searchseed == n // 2:
        searcher = [2]
    else:
        searcher = [1, 2]
    #print(searchseed)
    for search in itertools.product(searcher, repeat = searchseed):
        if not sum(search) == n:
             continue
        #print(search)
        position = 0
        flag = 0
        for step in search:
            position += step
            if position in a:
                break
            else:
                flag +=1
        if flag == len(searchlist):
            count +=1
print(count % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
mod =  1000000007
ret = [0] * (N+1)
ret[0] = 1
for i in range(1,N+1):
    if i in a:
        continue
    elif i == 1:
        ret[1] = 1
    else:
        ret[i] = ret[i-2] + ret[i-1]

print(ret[len(ret)-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
dp=[1]+[0]*100010
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        try:
            dp[i]=dp[i-1]+dp[i-2]
        except:
            dp[i]=dp[i-1]
        dp[i]%=1000000007
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(i) for i in input().split()]
a=[int(input()) for _ in range(m)]
dp=[1]+[0]*100010
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        try:
            dp[i]=dp[i-1]+dp[i-2]
        except:
            dp[i]=dp[i-1]
print(dp[n]%1000000007)

Submission status: Time Limit Exceeded

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

out_list = []
result_list = [1]
for x in range(m):
    out_list.append(int(input()))

for x in range(1, n+1):
  if x in out_list:
    result_list.append(0)
  elif x == 1:
    result_list.append(result_list[x - 1])
  else:
    result_list.append(result_list[x-1] + result_list[x-2])

print(result_list[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod

print(count[N])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]

count = [0] * (N+1)
count[0] = 1
mod = 10 ** 9 + 7
if 1 in A:
    if 2 in A:
        print(0)
        exit()
    count[2] = 1
    start = 3
else:
    count[1] = 1
    start = 2
for i in range(start, N+1):
    if i in A:
        continue
    count[i] = count[i-1] + count[i-2]
    count[i] %= mod

print(count[N])

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

length, nb_bad_steps = map(int, input().split())

bad_steps = []
for i in range(nb_bad_steps):
  bad_steps.append(int(input()))
  
ways = Queue()
nb_ways = 0
ways.put([0])
while not ways.empty():
  current_way = ways.get()  
  if current_way[-1] == length:
    nb_ways += 1
  else:
    if current_way[-1] + 1 not in bad_steps:
      new_way = current_way.copy()
      new_way.append(current_way[-1] + 1)
      ways.put(new_way)
    if current_way[-1] + 2 not in bad_steps and current_way[-1] + 2 <= length:
      new_way = current_way.copy()
      new_way.append(current_way[-1] + 2)
      ways.put(new_way)
      

print(nb_ways)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
A=[int(input()) for _ in range(M)]
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
	dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
	if i in A:
		dp[i]=0
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int, input().split()))
a = [int(input()) - 1 for i in range(M)]
memo = [0 for i in range(N)]

for i in range(N):
    if i in a:
        memo[i] = 0
        continue
    if i == 0:
        memo[i] = 1
        continue
    if i == 1:
        memo[i] = 1 + memo[0]
        continue
    memo[i] = (memo[i-1] + memo[i-2]) % 1000000007

print(memo[N-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

N,M = list(map(int, input().split()))
a = [int(input()) - 1 for i in range(M)]
memo = [0 for i in range(N)]

for i in range(N):
    if i in a:
        memo[i] = 0
        continue
    if i == 0:
        memo[i] = 1
        continue
    if i == 1:
        memo[i] = 1 + memo[0]
        continue
    memo[i] = memo[i-1] + memo[i-2]

print(memo[N-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

N,M = list(map(int, input().split()))
a = [int(input()) - 1 for i in range(M)]
memo = [-1 for i in range(N)]

def process(n): #n段目まで何通りでいけるか？
    if memo[n] != -1:
        return memo[n]
    if n == -1: # nが-1
        return 1
    if n < -1:
        return 0
    if n in a:
        memo[n] = 0
        return 0
    if n == 0:
        memo[0] = 1
        return 1
    cnt = process(n-1) + process(n-2)
    memo[n] = cnt
    return cnt

for i in range(N):
    process(i)

print(process(N-1) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
List = [int(input()) for _ in range(M)]

P = 1000000007

if N==1:
    print(1)
    
else:
    dp = [0]*(N+1)

    if 1 in List:
        dp[1] = 0
        if 2 in List:
            dp[2] = 0
        else:
            dp[2] = 1
    else:
        dp[1] = 1
        if 2 in List:
            dp[2] = 0
        else:
            dp[2] = 2

    for i in range(2, N):
        if i+1 in List:
            dp[i+1]=0
        else:
            if i in List:
                dp[i+1] = dp[i-1]
            else:
                dp[i+1] = (dp[i]+dp[i-1])
        
    print(dp[N]%P)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,[input() for i in range(M)]))

dp = {i:0 for i in A}

dp[0]=1 # 0段目
if 1 in A: # 1段目
  dp[1]=0
else :
  dp[1]=1

for i in range(2,N+1):  
  if i in A:
    continue
  else :
    dp[i]=dp[i-1]+dp[i-2]
print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
A = [int(input()) for i in range(M)]

dp = [0]*(N+1)
dp[0] = 1

for next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = (dp[next-1] + dp[next-2])%1000000007

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
A = [int(input()) for i in range(M)]

dp = [0]*(N+1)
dp[0] = 1

for next in range(1,N+1):
    if next in A:
        dp[next] = 0
    else:
        dp[next] = dp[next-1] + dp[next-2]

print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = list(map(int,[input() for i in range(M)]))
dp = []
dp.append(1) # 0段目
if 1 in A: # 1段目
  dp.append(0) 
else :
  dp.append(1) 

for i in range(2,N+1):  
  if i in A:
    dp.append(0)
  else :
    dp.append(dp[i-1]+dp[i-2])
print(dp[N]%1000000007)