TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

87.4% (235/269)

Submission's AC Ratio

46.0% (370/804)

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

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5