TopCoder

Thumb
MO
我好廢~~

User's AC Ratio

96.8% (61/63)

Submission's AC Ratio

34.7% (66/190)

Description

給你 $n$ 表示有 $2 \times n$ 的表格,例如 $n = 3$ 長得像這樣:
┌--┬--┬--┐
│a1│a2│a3│
├--┼--┼--┤
│b1│b2│b3│
└--┴--┴--┘

並且可保證對每個 $a_i < b_i ; a_i < a_{i+1} ; b_i < b_{i+1}$ 。

求將 $1 ~ 2n$ 擺進去且符合條件之方法數有幾種?

Input Format

給你$n$的值($1 \leq n < 20$)。

Output Format

請輸出答案~

Sample Input

1
2
3
4
5

Sample Output

1
2
5
14
42

Hints

提示:易知當 $n = 1$ 時答案為 $1$ ,即 $f(1)$ = $1$。

然後有遞迴式 $f(n) = \displaystyle\frac{4n-2}{n+1}f(n-1)$。

以此公式可算出正確解答,並且解答數字不會超過 int 之範圍。

Problem Source

原TIOJ1296 / TFcis9 留社考(prob 2)。Problem Setter:sa072686。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144