[翻譯][UVa][11173] Grey Codes

翻譯, UVa/ACM 本文总阅读量次

我們將用一種二分法的方式去產生一個數列，先從如下的數列開始：

1
2
0
1

將此數列依照水平線做鏡射，接著上半部的數列前面加 0，下半部前面加 1，你將會得到如下數列：

1
2
3
4
00
01
11
10

重覆此步驟，會再一次得到下面 8 個數字所構成的數列：

1
2
3
4
5
6
7
8
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4

這些 2 進位的數字的右側是其對應的數字。

而這些數列分別被稱為 1 位元、2 位元及 3 位元的格雷碼 (Reflected Gray Code，或稱為 Gray Code)，一個 n 位元的格雷碼由 $2^n$ 個不同的數字所組成，而此數列上的數字，和其所相鄰的數字都差一個位元。

輸入

第一行為一整數 N (不超過 250000)，代表接下來有 N 行測資。接下來的 N 行每行有兩個整數 n ($1\leq{n}\leq{30}$) 及 k ($0\leq{k}\leq{2^n}$）。

輸出

對於每個測資，請輸出在 n 位元上第 k 個位置的格雷碼。

範例輸入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7

範例輸出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
1
0
1
3
2
0
1
3
2
6
7
5
4
翻譯, UVa/ACM