d544北市賽 98 1-algae

內容：

根據最新的生態學研究報導，在台北市植物園的蓮花池中，發現了一種奇特的海藻，此種海藻的外形具有一種十分特殊的性質：

1. 種子落地後，經過一天的時間，會先長出一根長一公分的綠色分枝。
2. 綠色的分枝，經過一天的時間後，會向上成長一公分，並且變成黃色。
3. 黃色的分枝，經過一天的時間後，會向上成長一公分，並且分成左右兩個分枝，其中左分枝為綠色，右分枝為黃色。

所有的分枝都不會互相交錯，同時恰好成長在同一個平面上。

舉例來說，若我們由左而右俯視觀察此海藻每天的生長情形，則在種子落地後的第一天，觀察結果為『綠』，第二天的觀察結果為『黃』，第三天的觀察結果為『綠黃』，第四天的觀察結果為『黃綠黃』，第五天的觀察結果為『綠黃黃綠黃』，依此類推。

請寫一個程式，預測在第 N 天時，由左邊數來第 K 個分枝的顏色為何。

輸入說明：

每個測資點中的第一行有一個正整數 M 代表此測資點中共有 M 組測試資料

每組測試資料含有兩個以空白相間隔的正整數，分別依次為 N 與 K

為方便起見，所有的測試資料皆滿足 0 < M < 100，0 < N < 100 且 0 < K < 2000000000

輸出說明：

每行輸出第 N 天時

由左邊數來第 K 個分枝的顏色（請用數字 0 代表綠色，1 代表黃色）

若第 N 天時，此海藻的分枝數少於 K，則輸出 -1

範例輸入：

3 1

5 5

6 100

範例輸出：

-1

出處：

北市 98 資訊學科能力競賽

解題策略

DP與遞迴