TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

93.7% (59/63)

Submission's AC Ratio

48.1% (75/156)

Tags

Description

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

1. 種子落地後,經過一天的時間,會先長出一根長一公分的綠色分枝。
2. 綠色的分枝,經過一天的時間後,會向上成長一公分,並且變成黃色。
3. 黃色的分枝,經過一天的時間後,會向上成長一公分,並且分成左右兩個分枝,其中左分枝為綠色,右分枝為黃色。
4. 所有的分枝都不會互相交錯,同時恰好成長在同一個平面上。

舉例來說,若我們由左而右俯視觀察此海藻每天的生長情形,則在種子落地後的第一天,觀察結果為『綠』,第二天的觀察結果為『黃』,第三天的觀察結果為『綠黃』,第四天的觀察結果為『黃綠黃』, 第五天的觀察結果為『綠黃黃綠黃』,依此類推。請寫一個程式,預測在第N天時,由左邊數來第K個分枝的顏色為何。

Input Format

輸入檔中的第一行有一個正整數M,代表此輸入檔中共有M組測試資料。
接下來的M行中,每一行代表其中一組測試資料,含有兩個以空白相間隔的正整數,分別依次為N與K。
為方便起見,所有的測試資料皆滿足0<M<10,0<N<100,且0<K<2,000,000,000。

Output Format

請根據輸入檔的資料,依序在每一行中,輸出第N天時,由左邊數來第K個分枝的顏色(請用數字0代表綠色,1代表黃色)。
若第N天時,此海藻的分枝數少於K,則輸出-1。

Sample Input 1

1
3 1

Sample Output 1

0

Sample Input 2

3
3 1
5 5
6 100

Sample Output 2

0
1
-1

Hints

Problem Source

原TIOJ1677 / 98北市賽(prob 1)

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 (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5