e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Письмо Шарика из Простоквашино

prb401

Дорогой дядя Федор!

Не слушай этого старого ворчливого кота. Он еще не знает, какой я ему приготовил сюрприз, поэтому можете загодя писать для него программу. Я ему количество квадратиков со скобками увеличил до 300, количество заданий на день до 20, и усложнил само задание.

Теперь ему нужно искать вложенность правильных последовательностей скобок. Что это такое, я прочел в одной умной книжке, которую потерял почтальон Печкин. Там написано следующее:

"Пусть X - множество правильно построенных скобочных выражений. Длиной правильно построенного скобочного выражения E называется количество одиночных скобок в E. Вложенность D(E) выражения E определяется следующим образом:

prb401r

Например, длина ()(())() равна 8, а вложенность 2.

Понимая, что кот все-таки не человек, я ему даю такие задания, где вложенность не менее 1 и не более 200, а квадратиков со скобками выдаю не менее двух. Вот теперь он пусть поищет количество способов получить правильные скобочные последовательности заданных длины и вложенности.

Так что спеши выслать ему свою новую программу, ибо дою корову и молоко пью только я, пока Матроскин занят вычислениями. Фотографию задумчивого Матроскина прилагаю.

Твой верный друг и товарищ - Шарик"

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

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

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

Для каждого теста вывести в отдельной строке количество способов, которыми можно получить правильно построенное скобочное выражение длины n и глубины d.

Лимит времени 4 секунда
Лимит использования памяти 244.24 MiB
Входные данные #1
6 2
300 150
Выходные данные #1
3
1
Автор Анатолий Присяжнюк