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