BFS(0) = 0
BFS(1) = 1 (這裡的"0"與"1"為字串,並非數字的0與1)
對於所有 n > 1,BFS(n) = BFS(n-1) + BFS(n-1),這裡的 + 符號表示兩個字串的合併
故我們定義了一個新的字串序列:0, 1, 01, 101, 01101, ...。
請你寫一個程式找出序列中的第N個字串,並輸出該字串的第 i 個字元到第 j 個字元(N, i, j的序號皆以0開始)。
Input
輸入資料的第一列有一個整數T(T <= 100)表示測試資料的組數,每組資料有三個整數N, i, j (0 <= N, i, j < 2^31 且 i <= j 且 j - i <= 10000),資料保證不會超出範圍(即 0 <= i, j < BFS(N)字串長度)。Output
對於每組測試資料,請輸出BFS(N)中從 i ~ j 位置的字串。Sample Input
3
3 1 2
1 0 0
9 5 12
Sample Output
01
1
10101101
原文出處
沒有留言:
張貼留言