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 "(()())".

Feodor Volonter

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 |

Solve/Submission

# | 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 |

Copyright © 2015-2016 Dev Skill.

Feedback
#### Your feedback is our precious!

## Thank you for providing feedback! Our developers will be happy :)

## Sorry there was a problem when submitting the feedback. Please try again. :(