1719 測資加強 已 rejudge
1471 . 山景 Skyline
TopCoder
Tags
Description
一座山的山稜線由許多片段的45度斜坡構成，每一個片段不是上坡就是下坡。
* * * /\ * /\ /\/ \ /\/ \/ \
在我們眼前的所見的任何寬度為n個單位的山稜形狀，可以輕鬆地觀察到所有山頂的位置。
請問有多少種山稜線的形狀，使得所有山頂的位置由左而右非遞減呢？
所有的山稜線都必須完整，也就是說左右兩端都必須是高度為0的山腳，而且不能有任何山谷的位置隱沒在地平線底下。
Input Format
輸入僅包含一個數字n，n一定會是偶數，因為會有相同片段數量的上坡以及下坡。
Output Format
請輸出山頂位置由左而右非遞減的山稜線形狀總數。
由於答案可能很大，你只要輸出以十進位表示時，它的最後9位數即可。
Sample Input 1
6
Sample Output 1
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 |