TopCoder

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

User's AC Ratio

100.0% (21/21)

Submission's AC Ratio

69.1% (38/55)

Description

又是好多燈炮?不過這題沒那麼難。

現在有一排燈座,上面插滿了燈炮,不過為了省電,可以把幾個燈炮拔起來。但為了能夠有足夠的光線,第偶數位個燈炮如果拔起來了,相鄰的兩個燈炮就不行拔,以免太暗有些人會蠢蠢欲動做出糟糕的事出來。

現在給你燈座數,問有幾种放燈炮的方法?

Input Format

每一列有一個n(1<=n<=50),代表燈座數,結束條件為EOF。

Output Format

輸出一列,印出放燈炮的方法數。

Sample Input

3
6

Sample Output

5
21

Hints

對於n==3,可能的方法有:(0代表沒有,1代表有燈炮)
010
011
101
110
111
以上5種

Problem Source

原TIOJ1560 / 2009雄中公假社

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144