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×n 的表格，例如 n=3 長得像這樣：
┌--┬--┬--┐
│a1│a2│a3│
├--┼--┼--┤
│b1│b2│b3│
└--┴--┴--┘

並且可保證對每個 ai<bi；ai<ai+1；bi<bi+1 。

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

Input Format

給你n的值(1≤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)=4n−2n+1f(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