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

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

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

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

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

Примеры

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

5 4

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

8

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

Question

Информатика

Звенемира

2 августа, 02:21

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

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

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

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

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

Примеры

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

5 4

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

8

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

+3

Ответы (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])