DCP-514: Parenthesis Back to All Problems

Easy Divide and Conquer > Dynamic Programming


A string consisting of parenthesis '**(**' and '**)**' is called balanced string if any of the following is true. - If the string is empty. - If **A** and **B** are balanced strings, then **AB** is also balanced string. - If **A** is a balanced string, then (**A**) is also a balanced string. <p> Your task is to find the number of balanced strings of length **L** if each of them begins with **K** of symbols '('. Restrictions: **1 ≤ L ≤ 50**, **1 ≤ K ≤ L**. Input: ------ The first line of input consists of integer number **T** representing the number of test cases (**1 ≤ T ≤ 2000**). Each of the following lines specifies one test case and consists of two blank separated positive integers **L** and **K** denoting the length of balanced string and the number of it's first symbols '**(**'. Output: ------- For each test case, print a line "**Case X: Y**" where **X** is replaced by the test case number and **Y** is the number of balanced strings corresponding to the given values **L** and **K**. Sample Input ------------ 4 6 2 7 1 50 25 50 30 Sample Output ------------- Case 1: 3 Case 2: 0 Case 3: 1 Case 4: 0 Note ---- Explanation to the first test case: those three balanced strings are "((()))", "(())()" and "(()())".


Problem Setter:

Feodor Volonter

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

54/160

Solve/Submission

Ranking

# User Language Timing
01 mahbubcseju Cpp 0.00s
02 Zeronfinity Cpp 0.00s
03 CLown1331 Cpp14 0.00s
04 shaft Cpp14 0.00s
05 tariqiitju Cpp14 0.00s
06 Mr_adnan Cpp 0.00s
07 Masum_ice Cpp 0.00s
08 Hasinur_ Cpp 0.00s
09 IIUC_minhazmiraz Cpp14 0.00s
10 feodorv C 0.00s
11 kzvd4729 Cpp14 0.00s
12 mh755628 Cpp 0.00s
13 by_default C 0.00s
14 QuwsarOhi Cpp14 0.00s
15 radoslav11 Cpp 0.00s
16 BlueOcean Cpp 0.00s
17 Nobel Cpp 0.01s
18 KerimK Cpp 0.01s
19 Essux Cpp 0.01s
20 Mimsad Cpp14 0.01s
21 Ahb_arif Cpp 0.01s
22 nahid08 Cpp 0.01s
23 shahed95 Cpp 0.01s
24 PKP_Junior Cpp 0.01s
25 Bruteforcekid Cpp14 0.01s
26 emrul Cpp 0.01s
27 sakib_muhit Cpp 0.01s
28 rayhan50001 Cpp 0.01s
29 MAD_coder Cpp 0.01s
30 uzzal_rahman Cpp 0.01s
31 sdpsarker88 Cpp 0.01s
32 akazad_cse13_ruet Cpp 0.01s
33 dipta007 Cpp 0.01s
34 mamun4122 Cpp14 0.01s
35 ksohan Cpp 0.02s
36 AlaminJust Cpp 0.02s
37 hruday_kohli Cpp 0.02s
38 cjoa Cpp 0.02s
39 gultai4ukr Cpp14 0.03s
40 snow_man Cpp 0.05s
41 skmonirlive Cpp14 0.05s
42 swapnilsaha Cpp14 0.05s
43 Trumen Cpp 0.05s
44 Informatimukas Cpp 0.05s
45 robin_aust Cpp 0.06s
46 Sarwar05 Cpp 0.06s
47 Arpan_cse_2k14 Cpp 0.07s
48 MRoy Cpp 0.07s
49 showmic Cpp14 0.17s
50 BohdanPastuschak Java 0.69s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support