1007 . 燈泡問題
TopCoder
Tags
Description
我們有一些不同的燈泡，裡面都有一條燈絲，但品質都不是很好，如果持續地讓燈泡亮著的話，燈絲過一會兒就燒斷了，因此必須有時將電源切斷，讓燈絲降溫。
假設一個燈泡最多可以持續點亮 $n$ 單位的時間而不燒斷，而總時間是 $m$ 單位時間。請寫一個程式，給定 $n$ 和 $m$ 的值，算出有幾種不同的明暗排列方式，每一種排列方式之中都不會出現亮超過連續 $n$ 單位時間的區段。
Input Format
有兩個數字 $n$ 和 $m$ 以一個空白分開，其中 $1\le n\le 15$，$1\le m\le 90$。
Output Format
對於每一筆輸入請輸出一個數字，代表排列方式的總數。每個答案保證不會超過$2^{64}-1$，所以你不必考慮有大數的情況會發生。
Sample Input 1
2 4
Sample Output 1
13
Hints
範例輸出說明：
亮用○表示，暗用●表示，則有下面13種方式。
１ ●●●● ２ ○●●● ３ ●○●●
４ ●●○● ５ ●●●○ ６ ○○●●
７ ○●○● ８ ○●●○ ９ ●○○●
１０ ●○●○ １１ ●●○○ １２ ○○●○
１３ ○●○○
以下是不合題目敘述的方式。
１ ○○○○ ２ ●○○○ ３ ○○○●
Problem Source
原TIOJ1007 / 建國中學95學年度校內資訊能力競賽(4, bulb)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |