Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N. В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.

Входные данные

Входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что 1 ≤ N, K ≤ 32.

Выходные данные

Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N.

Примеры

Входные данные

5 4

Выходные данные

8

Программа должна быть на питоне

Question

Информатика

Осия

23 июня, 22:43

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N. В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.

Входные данные

Входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что 1 ≤ N, K ≤ 32.

Выходные данные

Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N.

Примеры

Входные данные

5 4

Выходные данные

8

Программа должна быть на питоне

+1

Ответы (1)

Знаешь ответ?

Ариней · Answer 1

n=int (input ())

k=int (input ())

a=[1]

for i in range (1, n):

for j in range (i-1, i-k-1,-1):

if j<0:

break

a. append (0)

a[i]+=a[j]

print (a[n-1])