Компьютерный центр г. Светлогорска

Найдите количество последовательностей из нулей и единиц длины \(n\), в которых никакие две единицы не стоят рядом.

n = int(input())

dp0 = [0] * (n + 1)
dp1 = [0] * (n + 1)
dp0[1] = dp1[1] = 1
for i in range(2, n + 1):
    dp0[i] = dp0[i-1] + dp1[i-1]
    dp1[i] = dp0[i-1]

ans = dp0[n] + dp1[n]
print(f"{ans}")

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от \(1\) до \(n\). В начале кузнечик сидит на столбике с номером \(1\). Он может прыгнуть вперёд на \(1\), \(3\) или \(5\) столбиков, считая от текущего. На некоторых столбиках сидят лягушки, которые едят кузнечиков (кузнечик не должен попадать на эти столбики). Определите, какое максимальное количество столбиков сможет посетить кузнечик на своём пути до столбика с номером \(n\). Если кузнечику не удастся оказаться в клетке с номером \(n\), выведите \(-1\).

n, k = map(int, input().split())
a = list(map(int, input().split()))

dp = [0] * (n + 1)
for ai in a:
    dp[ai] = -1
dp[1] = 1
for i in range(1, n):
    if dp[i] == -1:
        continue
    for j in [1, 3, 5]:
        if i + j <= n and dp[i+j] != -1:
            dp[i+j] = max(dp[i+j], dp[i] + 1)
if dp[n] == 0:
    dp[n] = -1
print(f"{dp[n]}")

Практические задания