SQRBR - Square Brackets
You are given:
- a positive integer n,
- an integer k, 1<=k<=n,
- an increasing sequence of k integers 0 < s1 < s2 < ... < sk <= 2n.
What is the number of proper bracket expressions of length 2n with opening brackets appearing in positions s1, s2 ... sk?
Illustration
Several proper bracket expressions:
[[]][[[]][]] [[[][]]][][[]]
An improper bracket expression:
[[[][]]][]][[]]
There is exactly one proper expression of length 8 with opening brackets in positions 2, 5 and 7.
Task
Write a program which for each data set from a sequence of several data sets:
- reads integers n, k and an increasing sequence of k integers from input,
- computes the number of proper bracket expressions of length 2n with opening brackets appearing at positions s1,s2, ... sk,
- writes the result to output.
Input
The first line of the input file contains one integer d, 1 <= d <= 10, which is the number of data sets. The data sets follow. Each data set occupies two lines of the input file. The first line contains two integers n and k separated by single space, 1 <= n <= 19, 1 <= k <= n. The second line contains an increasing sequence of k integers from the interval [1;2n] separated by single spaces.
Output
The i-th line of output should contain one integer - the number of proper bracket expressions of length 2n with opening brackets appearing at positions s1, s2 ... sk.
Example
Sample input: 5 1 1 1 1 1 2 2 1 1 3 1 2 4 2 5 7 Sample output: 1 0 2 3 2
hide comments
|
sdeven_0245:
2019-02-04 04:16:15
Easy dp
|
|
i_am_hokage:
2018-02-10 17:24:30
If it is your first problem on bracket sequence topic you may want to read about standard problems on that topic. Otherwise, It would be hard for you to determine transition between states. |
|
Rajivteja:
2017-12-29 10:17:53
Solved without hint :) Motivated. Last edit: 2017-12-29 10:18:49 |
|
ab_hi_shek111:
2017-09-12 23:07:26
solved and Motivated :) |
|
aditya9125:
2017-09-11 22:33:34
Try iterative DP, you will definitely enjoy. |
|
ashishranjan28:
2017-05-23 08:43:04
easy recursion :) |
|
sultania23:
2017-03-24 08:10:46
recursion with mem... nice one.. |
|
ayush_1997:
2017-02-21 19:06:27
nice problem :) |
|
Mayank Agarwal:
2017-01-29 20:39:28
nice dp:) |
|
sushantoberoi3:
2017-01-15 06:41:49
easy problem.. |
| Added by: | adrian |
| Date: | 2004-06-22 |
| Time limit: | 3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | III Polish Collegiate Team Programming Contest (AMPPZ), 1998 |
RSS