CSP-S2019 D1T1：格雷码（code） - Problem

通常，人们习惯将所有

n

位二进制串按照字典序排列，例如所有

2

位二进制串按字典序从小到大排列为：

00

，

01

，

10

，

11

。
格雷码（Gray Code）是一种特殊的

n

位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。
所有

2

位二进制串按照格雷码排列的一个例子为：

00

，

01

，

11

，

10

。

n

位格雷码不止一种，下面给出其中一种格雷码的生成算法：

1 位格雷码由两个一位二进制串组成，顺序为： $0$ ， $1$ 。
$n + 1$ 位格雷码的前 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按顺序排列，再在每个串前加一个前缀 $0$ 构成。
$n + 1$ 位格雷码的后 $2^n$ 个二进制串，可以由依此算法生成的 $n$ 位格雷码（总共 $2^n$ 个 $n$ 位二进制串）按逆序排列，再在每个串前加一个前缀 $1$ 构成。

综上，

n + 1

位格雷码，由

n

位格雷码的

2^n

个二进制串按顺序排列再加前缀

0

，和逆序排列再加前缀

1

构成，共

2^{n+1}

个二进制串。另外，对于

n

位格雷码中的

2^n

个二进制串，我们按上述算法得到的排列顺序将它们从

0

2^n-1

编号。
按该算法，

2

位格雷码可以这样推出：

已知 $1$ 位格雷码为 $0$ ， $1$ 。
前两个格雷码为 $00\textit{\textbf{0}}0$ ， $01\textit{\textbf{0}}1$ 。后两个格雷码为 $11\textit{\textbf{1}}1$ ， $10\textit{\textbf{1}}0$ 。合并得到 $00$ ， $01$ ， $11$ ， $10$ ，编号一次为 $0$ ~ $3$ 。

同理，

3

位格雷码可以这样推出：

已知 $2$ 位格雷码为： $00$ ， $01$ ， $11$ ， $10$ 。
前四个格雷码为： $000\textit{\textbf{0}}00$ ， $001\textit{\textbf{0}}01$ ， $011\textit{\textbf{0}}11$ ， $010\textit{\textbf{0}}10$ 。后四个格雷码为： $110\textit{\textbf{1}}10$ ， $111\textit{\textbf{1}}11$ ， $101\textit{\textbf{1}}01$ ， $100\textit{\textbf{1}}00$ 。合并得到： $000$ ， $001$ ， $011$ ， $010$ ， $110$ ， $111$ ， $101$ ， $100$ ，编号依次为 $0$ ~ $7$ 。

现在给出

n, k

，请你求出按上述算法生成的

n

位格雷码中的

k

号二进制串。

5080: CSP-S2019 D1T1：格雷码（code）

Description

Input

Output

Constraints

Sample 1 Input

Sample 1 Output

Sample 2 Input

Sample 2 Output

Sample 3 Input

Sample 3 Output

HINT

Source/Category

5080: CSP-S2019 D1T1：格雷码（code）

Description

Input

Output

Constraints

Sample 1 Input Copy

Sample 1 Output Copy

Sample 2 Input Copy

Sample 2 Output Copy

Sample 3 Input Copy

Sample 3 Output Copy