eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

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

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

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

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

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
6 2
300 150
Çıxış verilənləri #1
3
1
Müəllif Анатолий Присяжнюк