Решение задачи Кузнечик с Codeforces

Без пояснения   Просмотров: 2708

У одного из студентов в комнате живёт кузнечик, который очень любит прыгать по клетчатой одномерной доске. Длина доски — N клеток. К его сожалению, он умеет прыгать только на 1, 2, …, k клеток вперёд.

Однажды студентам стало интересно, сколькими способами кузнечик может допрыгать из первой клетки до последней. Помогите им ответить на этот вопрос.

Код 

n, k = map(int, input().split())
a = [0] * n
s = 1
if n == 1:
    print(1)
    raise SystemExit
for i in range(n - 2, n - 2 - k, -1):
    if i == -1:
        print(a[0])
        raise SystemExit
    a[i] = s
    s += a[i]
s = 2 ** k - 1
for i in range(n - 2 - k, -1, -1):
    a[i] = s
    s -= a[i + k]
    s += a[i]
print(a[0])

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp