Динамическое программирование

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, q_n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p_j = q_j при j < i и p_i < q_i.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

Входные данные
Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 10⁹). Вторая строка содержит n различных натуральных чисел, не превосходящих 10⁹. Все числа в строках разделены пробелом.

Выходные данные
В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 8 3 9	3 9 6 8
2	4 4 2 6 8 3 9	9 3 6 8
3	4 5 2 6 8 3 9	-1

Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.

Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.

Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел d_i1,d_i2, d_iN — длины дорог от i-й точки до всех остальных. Гарантируется, что d_ij=d_ji, d_ii=0 и 0 <d_ij <100. В (N+2)-й строке находится одно целое число Q (1 < Q ≤ 1000) — количество вариантов вычеркивания точек для данной карты. В последующих Q строках содержится описание вариантов вычеркивания. Описание начинается с числа C (0 ≤ C < N) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие C чисел задают номера этих точек.

Выходные данные
Выведите Q строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.

Примеры

№	Входные данные	Выходные данные
1	3 0  45 10 45 0  30 10 30 0 2 0 1 3	40 45
2	5 0  14 20 17 14 14 0  15 19 18 20 15 0  15 16 17 19 15 0  14 14 18 16 14 0 2 3 5 4 3 0	14 58

Сколько целых последовательностей длины N, A = (A₁,…,A_N), удовлетворяют всем приведенным ниже условиям?
1) 1 <= A_i <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).

Выходные данные
Выведите на ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 4	6	(1,1) (1,2) (1,3) (2,1) (2,2) (3,1)

Дана строка, состоящая из прописных латинских букв. Можно удалять из этой строки все пары соседних одинаковых букв, включая пары, образовавшиеся после удаления других пар. Нужно заменить в заданной строке 0 или более букв так, чтобы после удаления всех пар строка стала пустой.

Входные данные:
Первая строка содержит одну строку четной длины от 2 до 200, состоящую из строчных букв латинского алфавита.

Выходные данные:
В первой строке вывести минимальное количество замен букв.

Пример:
 

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

Пояснение:
Можно заменить шестую букву на b, тогда процесс удаления будет выглядеть следующим образом: baddabcc -> baddab -> baab -> bb ->  .
 

Хлоя недавно установила на свой телефон игру «Zuma». Игроку даётся ряд из n драгоценных камней, i-й из которых имеет цвет c_i. Цель игры — уничтожить все камни за как можно меньшее количество секунд.

За одну секунду Хлоя может выбрать любую подстроку (последовательность стоящих рядом камней), являющуюся палиндромом, и удалить её. После удаления данной подстроки оставшиеся камни сдвигаются, чтобы снова образовать непрерывный ряд. Какое минимальное количество секунд необходимо, чтобы уничтожить всю строку?

Напомним, что строка (или подстрока) является палиндромом, если она одинаково читается как слева направо, так и справа налево. В данном случае это означает, что цвет первого камня равен цвету последнего камня, цвет второго равен цвету предпоследнего и так далее.

Входные данные:
В первой строке входных данных записано единственное число n (1 ≤ n ≤ 500) — количество камней в изначальном ряду.
Во второй строке записано n целых чисел, i-е из которых равно c_i (1 ≤ c_i ≤ n) — цвет i-го камня в изначальном ряду.

Выходные данные:
Выведите единственное целое число — минимальное количество секунд, необходимое чтобы удалить все камни.

Примеры:
 

Входные данные	Выходные данные
3 1 2 1	1
3 1 2 3	3
7 1 4 4 2 3 2 1	2

Пояснения:
Последовательность в третьем примере: [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []

Вам дана полоска из клетчатой бумаги из n раскрашенных квадратов, пронумерованных от 1 до n слева направо. Квадрат под номером i изначально покрашен в цвет c_i.

Скажем, что квадраты i и j лежат в одной компоненте, если c_i = c_j и c_i = c_k для всех k, удовлетворяющих i < k < j. Иначе говоря, все квадраты на отрезке от i до j должны иметь одинаковый цвет.
Например, у полоски [3,3,3] есть 1 компонента связности, а у [5,2,4,4] их 3.

Игра «заливка» играется на этой полоске следующим образом:
В начале игры вы выбираете один произвольный стартовый квадрат (это не считается за ход).
Затем, в каждый ход, вы меняете цвет компоненты связности, содержащей стартовый квадрат на любой другой цвет.

Выясните минимальное количество ходов, которое нужно, чтобы перекрасить всю полоску в один цвет.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 5000) — количество квадратов.

Вторая строка содержит целые числа c₁,c₂,…,c_n (1 ≤ c_i ≤ 5000) — изначальные цвета квадратов.

Выходные данные:
Выведите одно целое число — минимальное количество ходов, которое нужно сделать.

Примеры:
 

Входные данные	Выходные данные
4 5 2 2 1	2
8 4 5 2 2 1 3 5 5	4
1 4	0

Пояснение:
Один из оптимальных способов в первом примере: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени s_i. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть t_i минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение i-й задачи участник получает c_i баллов.

Артур, представляющий на межрегиональной олимпиаде один из региональных центров искусственного интеллекта, понимает, что важную роль на такой олимпиаде играет не только умение решать задачи, но и правильный стратегический расчет того, какие задачи надо решать, а какие пропустить. Ему, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной, сколько времени будет отведено на ее решение и сколько баллов можно получить за ее решение. Артур является талантливым школьником и поэтому сможет успешно решить за отведенное время и сдать на проверку любую задачу, которую он выберет для решения на олимпиаде.

Требуется написать программу, которая определяет, какое максимальное количество баллов Артур сможет получить при оптимальном выборе задач, которые он будет решать, а также количество и перечень таких задач.

Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) количество задач на олимпиаде.

Последующие n строк содержат описания задач, по три числа на каждой строке: si момент появления i-й задачи в минутах, t_i время, отведенное на ее решение в минутах, и ci сколько баллов получит участник за решение этой задачи (1 ≤ s_i, t_i, c_i ≤ 10⁹).

Выходные данные
Первая строка  должна содержать одно число – максимальное количество баллов, которое сможет получить Артур на олимпиаде.

Вторая строка должна содержать одно целое число m - количество задач, которые надо решить при оптимальном выборе.

Третья строка должна содержать m разделенных пробелом целых чисел - номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.

Если оптимальных ответов несколько, необходимо вывести любой из них.

Примеры

№	Входные данные	Выходные данные
1	2 1 1 1 2 2 2	3 2 1 2
2	3 1 2 1 3 2 1 2 4 3	3 1 3

У Макс в блокноте были записаны две строки s длины n и t длины m, состоящие из букв «a» и «b» латинского алфавита. Причем Макс знает, что строка t имеет вид «abab...», то есть на нечетных позициях строки стоит буква «a», а на четных — «b».

Вдруг утром Макс обнаружила, что кто-то испортил ее строку s. Некоторые буквы s были заменены на символ «?».

Назовем последовательность позиций i, i + 1, ..., i + m - 1 вхождением строки t в s, если 1 ≤ i ≤ n - m + 1 и t₁ = s_i, t₂ = s_i + 1, ..., t_m = s_{i + m - 1}.

Красота строки s оценивается как максимальное количество непересекающихся вхождений строки t в нее. Макс может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Макс хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов она хочет заменить как можно меньше символов «?». Найдите, сколько замен она должна сделать.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) — длину строки s.
Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».
Третья строка содержит целое число m (1 ≤ m ≤ 10⁵) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.

Выходные данные:
Выведите единственное целое число — минимальное количество замен, которое должен сделать Вася, чтобы сделать красоту строки s максимально возможной.

Примеры:
 

Входные данные	Выходные данные
5 bb?a? 1	2
9 ab??ab??? 3	2

Пояснения:
В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».
Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.

Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета l_i и моментом конца r_i (l_i ≤ r_i).

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

Никакие два принятых заказа не могут пересекаться, то есть не должно существовать момента времени, который принадлежит сразу двум принятым заказам. Если один из заказов начинается в момент, когда заканчивается другой, то они не могут быть приняты вместе.

Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел l_i, r_i (0 ≤ l_i ≤ r_i ≤ 10⁹).

Выходные данные:
Выведите наибольшее количество заказов, которые могут быть приняты.

Примеры:
 

Входные данные	Выходные данные
2 7 11 4 7	1
5 1 2 2 3 3 4 4 5 5 6	3
6 4 8 1 5 4 7 2 5 1 3 6 8	2

Хлоя хочет написать письмо своей подруге. Письмо - строка s, состоящая из строчных латинских букв.
К сожалению, как только Хлоя начала писать письмо, она поняла, что оно слишком длинное, и писать его целиком придётся очень долго. Поэтому она хочет написать сжатую версию строки s вместо самой строки.

Сжатая версия строки s — последовательность строк c₁, s₁, c₂, s₂, ..., c_k, s_k, где c_i — десятичная запись числа a_i (без лидирующих нулей), а s_i — некоторая строка из строчных латинских букв. Если Хлоя запишет строку s₁ ровно a₁ раз, потом s₂ ровно a₂ раз, и так далее, у нее получится строка s.
Длина сжатой версии равна |c₁| + |s₁| + |c₂| + |s₂|... |c_k| + |s_k|. Среди всех сжатых версий Хлоя хочет выбрать такую, что её длина минимальна. Помогите Хлое определить минимально возможную длину.

Входные данные:
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 5000).

Выходные данные:
Выведите одно целое число — минимальную длину сжатой версии строки s.

Примеры:
 

Входные данные	Выходные данные
aaaaaaaaaa	3
abcab	6
cczabababab	7

Пояснения:
В первом примере Хлоя выберет следующую версию: c₁ — 10, s₁ — a.
Во втором примере Хлоя выберет следующую версию: c₁ — 1, s₁ — abcab.
В третьем примере Хлоя выберет следующую версию: c₁ — 2, s₁ — c, c₂ — 1, s₂ — z, c₃ — 4, s₃ — ab.
 

Вам дан массив из n целых чисел. Вам необходимо разделить его на k непустых подотрезков (последовательность подряд идущих элементов) так, чтобы:
1) Каждый элемент массива входил ровно в один подотрезок.
2) Если для каждого подотрезка выбрать минимальное в нем число, то сумма всех минимумов должна быть максимально возможной.

Сообщите сумму минимумов значений в подотрезках этого разбиения.

Входные данные:
В первой строке дается два натуральных числа - n (1 <= n <= 500) и k (1 <= k <= n).
Во второй строке дается n целых чисел - элементы массива a_i (1 <= a_i <= 10⁵).

Выходные данные:
Выведите одно число - ответ на задачу.

Пример:
 

Входные данные	Выходные данные
5 3 4 2 5 1 3	8

Пояснение:
Одно из подходящих разбиений: [4, 2], [5], [1, 3]. Сумма минимумов в каждом подотрезке равна 2 + 5 + 1 = 8.

Макс находится на начальной станции поезда, и сейчас в него хотят зайти n человек (включая саму Макс). Они уже выстроились в некотором порядке, и для каждого из них известен код города a_i, в который они направляются.

Начальник поезда выбирает некоторое количество непересекающихся отрезков исходной последовательности людей (отрезки не обязаны покрывать всю последовательность). Люди, находящиеся в одном и том же отрезке, будут находиться в одном и том же вагоне поезда. Отрезки выбираются так, что если в город X едет как минимум один человек, то все люди, которые направляются в город X должны будут находиться в одном вагоне. Это обозначает, что они не имеют права принадлежать разным отрезкам. Следует заметить, что все люди, которые едут в город X, либо едут в него и находятся в одном вагоне, либо вовсе не едут никуда.

Комфортность поездки в поезде с людьми на отрезке с l по r равна XOR-у различных кодов городов у людей на отрезке с l по r. Операция XOR также известна как исключающее побитовое ИЛИ.

Общая комфортность выбранных отрезков вычисляется как сумма комфортности каждого отдельного отрезка.

Помогите Макс узнать максимальную достижимую общую комфортность.

Входные данные:
Первая строка содержит натуральное число n - число людей (1 <= n <= 5000).
Вторая строка содержит n целых чисел a_i (0 <= a_i <= 5000) - код города, в который направляется i-й человек.

Выходные данные:
Выведите одно целое число - максимальную общую комфортность.

Примеры:
 

Входные данные	Выходные данные
6 4 4 2 5 2 3	14
9 5 1 3 1 5 2 4 2 5	9

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А – 1, Б – 2, …, Я – 33), а пробел – нулем. 
Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Входные данные:
В первой строке содержится последовательность из не более чем 70 цифр.

Выходные данные:
Выведите одно число - количество возможных сообщений.

Пример:
 

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

Дочь короля Флатландии собирается выйти за прекрасного принца. 
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.

В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i. 
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.

Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].

Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10¹⁸).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10¹⁵).

Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе. 
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.

Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.

Примеры:
 

Входные данные	Выходные данные
3 6 8 3 10 7 3 8 2	1 2

Казума путешествует с тремя спутницами: Аквой, Мегумин и Даркнесс. Но за путешествия не платят, поэтому нашему отряду необходимо выполнять задания, порученные гильдией авантюристов.

Казума уже выбрал n заданий, которые необходимо выполнить. Однако всегда, когда отряд в полном сборе берется за что-то, то происходят непредвиденные и абсурдные вещи. Именно поэтому Казума решил, что на каждое из заданий он возьмет ровно двух спутниц.

Отношение каждой из спутниц к Казуме характеризуется целым числом. Изначально отношение каждой из них нейтрально и равно 0. В процессе выполнения задания отношение девушек, которых он взял на задание, к нему меняется в положительную или отрицательную сторону (а может и не меняться вовсе).

Для каждого из заданий Казума знает, как изменится отношение каждой девушки к нему после выполнения поручения. Он хочет брать спутниц на задания так, чтобы после выполнения всех, отношения всех девушек к нему были равны. Если этого можно добиться разными способами, то, конечно, необходимо, чтобы отношение было как можно лучше.

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

Входные данные:
В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения.
Следующие n строк содержат описание заданий — i-я строка содержит три числа a_i, m_i, d_i — величины, на которые изменятся отношения к Казуме Аквы, Мегумин или Даркнесс соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания. 
Все числа во входных данных целые и не превышают по абсолютному значению 10⁷.

Выходные данные:
В случае, если решения не существует, в первой строке выведите "Impossible".
В противном случае выведите отношение, которое будет у всех девушек по отношению к Казуме и при этом максимально возможное.

Примеры:
 

Входные данные	Выходные данные
3 1 0 0 0 1 0 0 0 1	1
7 0 8 9 5 9 -2 6 -8 -7 9 4 5 -4 -9 9 -4 5 2 -6 8 -7	5
2 1 0 0 1 1 0	Impossible

Задано прямоугольное поле размера n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (n,m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только вниз или вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее ИЛИ всех чисел на пути должно быть равно k.
Найдите количество подходящих путей для заданного поля.

Входные данные
Первая строка содержит три целых числа n, m и k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - высота и ширина поля, и число k.
Следующие n строк содержат по m целых чисел ai,j, где j-й элемент i-й строки равен ai,j (0 <= a_i,j <= 10¹⁸).

Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.
 

Примеры

№	Входные данные	Выходные данные
1	3 3 11 2 1 5 7 10 0 12 6 4	3
2	3 4 2 1 3 3 3 0 3 3 2 3 0 1 1	5

Дан массив A, состоящий из n целых положительных чисел, и число m. Выберите последовательность позиций B1, B2, ..., Bk (1 <= B₁ < B₂ < ... < B_k <= n) такую, чтобы значение  \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) было максимально (то есть, чтобы остаток от деления суммы элементов подпоследовательности на число m был максимально возможным). Выбранная последовательность может быть пустой.
Посчитайте максимальное возможно значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Входные данные
В первой строке даны два целых числа n и m (1 <= n <= 35, 1 <= m <= 10⁹). Во второй строке дано n целых чисел A1, A2, ..., An (1 <= A_i <= 10⁹)

Выходные данные
Выведите одно число - максимальное значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

 

Примеры

№	Входные данные	Выходные данные
1	4 4 5 2 4 1	3
2	3 20 199 41 299	19

 

Пояснения

В первом примере можно выбрать B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
Во втором примере можно выбрать B = {3}.

В связи с приближающимся завершением эпидемии коронавируса правительство города Энска приняло решение отправить на южные морские курорты отличников школ города - N отдыхающих.
В авиакомпаниях для перевозки имеются K типов самолётов с различным количеством пассажирских мест (P₁, P₂,...,P_k). Необходимо решить логистическую задачу: зарезервировать необходимое количество рейсов (R₁, R₂,...,R_k).
Суммарное количество посадочных мест не может быть меньше, чем количество пассажиров, а общее количество незанятых пассажирских мест (V) должно быть минимальным. Если будет обнаружено несколько вариантов, одинаковых по количеству незанятых мест, то следует выбрать вариант с меньшим общим количеством рейсов самолётов. Если и таких вариантов будет несколько, то нужно вывести любой из них.
Входные данные
в первой строке через пробел записаны 2 натуральных числа N и K, во второй - K натуральных чисел P₁ P₂ … P_k. N не превышает 10000, K не превышает 20, любое P_i меньше 500.
Выходные данные
в первой строке вывести число V, во второй через пробел вывести R₁ R₂ … R_k. Порядок количеств рейсов должен соответствовать исходному порядку типов самолётов.

Примеры

№	Входные данные	Выходные данные
1	1000 3 300 220 150	30 0 0 4 1
2	80 4 100 50 40 30	0 0 1 0 1 (вариант - 0 0 2 0)

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

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 8).

Выходные данные
Выведите все правильные скобочные последовательности по возрастанию в лексикографическом порядке. Каждую в отдельной строке.