1296 . 第二題　擺數字問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

seanhung21

User's AC Ratio

98.1% (106/108)

Submission's AC Ratio

38.5% (115/299)

Tags

TFcis IX-TFcis

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

1
2
3
4
5

Sample Output 1

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 (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
Submit
Back to Top