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


Задача

11 /16


Ладья Громозеки


Задача

Любимая шахматная фигура Громозеки - это ладья. Но он любит ходить ей только по вертикали, причем либо на одну клетку, либо на две. Громозека заканчивает игру, когда ладья доходит до конца вертикали. Подумав над очередной позицией, он заметил, что некоторые клетки на пути ладьи находятся под ударом фигур соперника и ходить на эти клетки нельзя.
Помогите Громозеке посчитать сколькими способами он может перевести ладью c 1 горизонтали на другой конец шахматного поля, не попадая на клетки под ударом. 

Входные данные
В первой строке вводится одно натуральное число N (N <= 40): размер шахматного поля. Во второй строке вводится одно натуральное число K (K <= N): количество клеток, находящихся под ударом. В третьей строке вводятся K различных натуральных чисел в диапазоне от 1 до N: номера клеток, находящихся под ударом фигур соперника.

Выходные данные
Выведите одно число  - количество способов попасть на конец вертикали (на N-ю клетку).
 
Примеры
Входные данные Выходные данные
1 7
2
3 5
1
2 10
3
5 1 2
0
3 3
1
2
1

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

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