TopCoder

Thumb 100
sine
喵喵喵

User's AC Ratio

97.7% (43/44)

Submission's AC Ratio

60.2% (50/83)

Description

某學校有一片狹長形狀的畸零地,其寬度、長度分別為30公分及n×10公分(其中 n 為輸入之值,n為奇數,n>=3),但在西北角缺了寬度、長度均為10公分的一角。現在我們要使用 (3×n-1)/2 塊磁磚將此片畸零地鋪滿,每塊磁磚的寬度、長度均為10公分及20公分,我們想知道共有多少種鋪法。請你撰寫一個程式來求出答案。以下圖為例,當 n=3 時,可看出共有4種不同的鋪法。

當n=5時,由下圖,可看出共有15種不同的鋪法。

Constraints

n為奇數,3<=n<=41。

Input Format

輸入檔可能包含多筆測試資料。每筆測試資料佔一列,包含一個正整數n。

Output Format

以螢幕輸出資料為不同鋪法的次數。注意:輸出之整數值可能多達12位數。

Sample Input

3
5

Sample Output

4
15

Hints

Problem Source

原TIOJ1127 / 94北市賽(prob 3)。Special thanks: kelvin。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

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