[Solution] Sherlock and Parentheses Kick Start Solution

[Solution] Sherlock and Parentheses Kick Start Solution

Sherlock and Watson have recently enrolled in a computer programming course. Today, the tutor taught them about the balanced parentheses problem. A string S$S$ consisting only of characters ( and/or ) is balanced if:

• It is an empty string, or:
• It has the form (S$S$), where S$S$ is a balanced string, or:
• It has the form S1S2$S_1{S}_2$, where S1$S_1$ is a balanced string and S2$S_2$ is a balanced string.

Sherlock coded up the solution very quickly and started bragging about how good he is, so Watson gave him a problem to test his knowledge. He asked Sherlock to generate a string S$S$ of `L + R` characters, in which there are a total of L$L$ left parentheses ( and a total of R$R$ right parentheses ). Moreover, the string must have as many different balanced non-empty substrings as possible. (Two substrings are considered different as long as they start and end at different indexes of the string, even if their content happens to be the same). Note that S$S$ itself does not have to be balanced.
Sherlock is sure that once he knows the maximum possible number of balanced non-empty

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

substrings, he will be able to solve the problem. Can you help him find that maximum number?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
Each test case consists of one line with two integers: L$L$ and R$R$.

Sherlock and Parentheses Kick Start Solution

Building Palindromes Kick Start Solution

Irregular Expressions Kick Start Solution

Parcels Kick Start Solution

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1$1$) and y$y$ is the answer, as described above.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.

Test Set 1

0≤L≤20$0\le \mathbf{L}\le 20$.
0≤R≤20$0\le \mathbf{R}\le 20$.
1≤L+R≤20$1\le \mathbf{L}+\mathbf{R}\le 20$.

Test Set 2

0≤L≤105$0\le \mathbf{L}\le {10}^5$.
0≤R≤105$0\le \mathbf{R}\le {10}^5$.
1≤L+R≤105$1\le \mathbf{L}+\mathbf{R}\le {10}^5$.