Problem C
Gray Code
Input: standard
input
Output: standard output
Time Limit: 2
seconds
Memory Limit: 32 MB
All of you know about Gray Code. It is a number code where consecutive numbers are represented by binary patterns that differ in one bit position only. In the following 4 examples of 3-bit gray code are shown :
In this problem we will deal with a gray code generation logic. This logic will generate the n-bit gray code using the coding of (n-1) bits. Lets formally define the rules :
Each gray code has a starting bit pattern. Such as "0 0 0" or "1 0 1" etc.
An n-bit gray code will have 2^n rows and two consecutive rows will differ by only one bit.
Each bit pattren will be present exactly once.
Gray code for 1-bit is trivial. Start with a bit and invert it in the next row.
To construct n-bit gray code keep
any of the n bits fixed (either 0 or 1) for the first 2^(n-1) rows and use
(n-1)-bit gray code (generated using this logic) for remaining (n-1) bits. Then
invert the fixed bit for the next 2^(n-1) rows and also use (n-1)-bit gray code
for remaining (n-1) bits whose bit pattern of the first row is the same as the
bit pattern of the last row of previous 2^(n-1) rows. For example 2-bit gray
code starting with "00" may be :
Simmilarly 2-bit gray code
starting with "01" may be :
If you observe carefully, you will see that the 3-bit gray codes given above are also constructed using this logic. Many such gray codes are possible for a particular starting bit pattern. We can order them from 1 to G(n) where G(n) denotes the number of such gray codes for n-bit. In our ordering scheme :
1st n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and also 1st (n-1)-bit gray code for lower half.
G(n-1)'th n-bit gray code has its leftmost bit fixed and it uses 1st (n-1)-bit gray code for upper half and G(n-1)'th (n-1)-bit gray code for lower half.
[G(n-1)+1]'th n-bit gray code has its leftmost bit fixed and it uses 2nd (n-1)-bit gray code for upper half and 1st (n-1)-bit gray code for lower half.
G(n)'th n-bit gray code has its
rightmost bit fixed and it uses G(n-1)'th (n-1)-bit gray code for both
halves.
You have to find a n-bit gray code for given starting bit pattern and
index.
Input
The first line of the input file contains a single integer N (0<N<=1000) which denotes the number of inputs. Each of the next N lines contains a string of bits for starting bit pattern and an integer for index. Number of bits will be between 1 to 6. And the index will be valid.
Output
Print the gray code for the given starting bit pattern and index. Put a blank line between two consecutive sets of inputs.
Sample
Input Sample
Output
Author : Md. Kamruzzaman
The Real Programmers' Contest-2