Код Грея#6005

Код Грея

1 секунда

64 мегабайти

Дуже легка

Коди Грея — це двійкова система нумерації, в якій два послідовні значення відрізняються лише одним бітом. Кожен $N$ -бітовий код Грея складається з $N$ бітів. Найпростіший випадок — це коли $N = 1$ N = 1, де коди Грея є $0$ і $1$ .

Розглянемо набір $N$ -бітових кодів Грея. Щоб отримати $(N + 1)$ (N + 1)-бітові коди Грея, можна скористатися простим методом. Спочатку запишіть наявні коди в стовпчик, проведіть лінію під останнім кодом, а потім "відобразіть" ці коди під лінією, тобто продублюйте список у зворотному порядку. Додайте $0$ перед початковими кодами і $1$ перед "відображеними". (Саме тому коди Грея також називають "відображеними бінарними кодами".)

Розглянемо приклад побудови кодів Грея для $N = 2$ N = 2:

Список кодів Грея для $N = 2$ N = 2 виглядає так: $00$ , $01$ , $11$ , $10$ .

Ось як можна згенерувати коди Грея для $N = 3$ N = 3:

Ваше завдання — обчислити та вивести лише $k$ -ий код $N$ -бітових кодів Грея. Коди нумеруються з $0$ . Наприклад, якщо $N = 3$ N = 3 і $k = 4$ k = 4, програма повинна вивести $110$ .

Вхідні дані

Вхідні дані складаються з кількох тестів. Кожен тест — це один рядок, що містить значення $N$ ( $1 \leq N \leq 72$ 1 \le N \le 72) і $k$ ( $0 \leq k \leq 2^{N} - 1$ 0 \le k \le 2^N-1). Останній рядок містить два нулі і не обробляється.

Зверніть увагу, що значення $k$ може не вміщатися в $32$ біт або навіть у $64$ біт. Також важливо не обчислювати всі $2^{N}$ 2^N значення коду Грея, а зосередитися на обчисленні лише $k$ -го значення.

Вихідні дані

Для кожного вхідного випадку виведіть номер випадку ( $1$ , $2$ , …), значення $N$ і $k$ , та $k$ -те значення коду Грея (позначене як "g"). Дотримуйтесь формату, показаного в прикладах нижче.

Приклади

Приклад 1