TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

37.5% (6/16)

Description

一座山的山稜線由許多片段的45度斜坡構成,每一個片段不是上坡就是下坡。

          *
   *   *  /\
*  /\  /\/  \
/\/  \/      \

在我們眼前的所見的任何寬度為n個單位的山稜形狀,可以輕鬆地觀察到所有山頂的位置。

請問有多少種山稜線的形狀,使得所有山頂的位置由左而右非遞減呢?

所有的山稜線都必須完整,也就是說左右兩端都必須是高度為0的山腳,而且不能有任何山谷的位置隱沒在地平線底下。

Input Format

輸入僅包含一個數字n,n一定會是偶數,因為會有相同片段數量的上坡以及下坡。

Output Format

請輸出山頂位置由左而右非遞減的山稜線形狀總數。
由於答案可能很大,你只要輸出以十進位表示時,它的最後9位數即可。

Sample Input

6

Sample Output

4

Hints

佔總分20%的測試數據中 n<=60
佔總分40%的測試數據中 n<=200
佔總分100%的測試數據中 n<=3000

Problem Source

原TIOJ1471 / CSAPC'08 Problem Setter: Tmt, Seanwu

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
5 900 65536 262144 6
6 900 65536 262144 7
7 900 65536 262144 8
8 900 65536 262144 9
9 900 65536 262144 10
10 900 65536 262144 11