No.790 Chicken's Parenthesis Arrangement
タグ : / 解いたユーザー数 174
作問者 :
severrabaen
/ テスター :
Kuske
Problem Statement
Chicken has $N$ characters '(' and $N$ characters ')' (the ' is not part of the characters). Chicken wants to know how many balanced parenthesis sequences in total can be made using all of these two kinds of characters. Here, a balanced parenthesis sequence must satisfy the definition at the end of the problem statement. On behalf of Chicken, please output how many balanced parenthesis sequences can be made in total.
Definition:
・The empty string satisfies the condition of a correct parenthesis sequence.
・If a string $s$ satisfies the condition of a correct parenthesis sequence, then ($s$) is a correct parenthesis sequence.
・If strings $s$ and $t$ both satisfy the condition of a correct parenthesis sequence, then the string obtained by concatenating $s$ and $t$ is a correct parenthesis sequence.
Input
$N$
The first line gives the number $N(1 \le N \le 13)$ of parentheses that Chicken has.
Output
Output the number of balanced parenthesis sequences, followed by a newline.
Sample
Sample 1
Input
2
Output
2
Only the 2 sequences (()) and ()() are balanced parenthesis sequences. For example, ())( is not a balanced parenthesis sequence because its parentheses are not completely closed.
Sample 2
Input
3
Output
5
The 5 sequences ((())), ()()(), ()(()), (())(), and (()()) satisfy the condition. For example, ())(() is not acceptable, as it does not satisfy the definition.
Note that the 3rd and 4th ones are counted as different strings.
Sample 3
Input
11
Output
58786
That's a lot, isn't it?
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。