TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

86.3% (151/175)

Submission's AC Ratio

46.3% (251/542)

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

2 4

Sample Output

13

Hints

範例輸出說明:

亮用○表示,暗用●表示,則有下面13種方式。

 1 ●●●●    2 ○●●●    3 ●○●●
 4 ●●○●    5 ●●●○    6 ○○●●
 7 ○●○●    8 ○●●○    9 ●○○●
10 ●○●○   11 ●●○○   12 ○○●○
13 ○●○○

以下是不合題目敘述的方式。

 1 ○○○○    2 ●○○○    3 ○○○●

Problem Source

原TIOJ1007 / 建國中學95學年度校內資訊能力競賽(4, bulb)

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536
1 10000 65536 65536
2 10000 65536 65536
3 10000 65536 65536
4 10000 65536 65536