Gray Code
Коды Грея представляют собой двоичную систему нумерации, в которой два последовательных значения отличаются только в одном бите. Каждый код N-битовых кодов Грея содержит N бит. Наиболее простой случай при N = 1, когда кодами Грея являются 0 и 1.
Пусть имеется набор N-битовых кодов Грея. Тогда N + 1 - битовые коды Грея строятся довольно просто. Выпишем имеющиеся коды в столбик, подведем линию под последним кодом, и "отразим" существующие коды под линией. То есть продублируем список в обратном порядке. Добавим 0 бит перед исходными кодами и 1 бит перед только что "отраженными". (поэтому коды Грея называются также "отраженными бинарными кодами.")
Рассмотрим построение кодов Грея для N = 2:
Список кодов Грея для N = 2 имеет вид: 00, 01, 11, 10.
Вот как можно сгенерировать коды Грея для N = 3:
Вам следует вычислить и вывести только k-ый код N-битовых кодов Грея. Коды нумеруются с 0. Если N = 3 и k = 4, то программа должна вывести 110.
Входные данные
Состоит из нескольких тестов. Каждый тест представляет собой одну строку, содержащую значения N (1 ≤ N ≤ 72) и k (0 ≤ k ≤ 2^N−1). Последняя строка содержит два нуля и не обрабатывается.
If it isn't immediately obvious from the preceding text, note that the value of k may not fit in a 32 bit or even a 64bit integer. It should also be noted that you will not want to compute all 2^N gray code values, but focus your attention on the computation of only the k-th such value.
Выходные данные
For each input case display the case number (1, 2, …), the values of N and k, and the k-th Gray code value (labeled as "g'). Follow the format shown in the samples below.