TopCoder

Thumb
MO
我好廢~~

User's AC Ratio

97.6% (80/82)

Submission's AC Ratio

36.2% (87/240)

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

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3