Модуль: 11.1d Динамическое программирование. Часть 4_Одномерная динамика


Задача

12 /16


Кузнечик и лягушки


Задача

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.
 
На некоторых столбиках сидят лягушки, которые едят кузнечиков (Кузнечик не должен попадать на эти столбики!). Определите, сколькими способами Кузнечик может безопасно добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.
 
Входные данные
Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 <= N, K <=  32 . Во второй строке записано число лягушек L ( 0 <= L <= N - 2 ). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N ).
 
Выходные данные
Программа должна вывести одно число: количество способов, которыми Кузнечик может безопасно добраться до столбика с номером N .

 
Примеры
Входные данные Выходные данные
1 6 4
2
2 4
3

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6428
Python3
Комментарий учителя