1999-2000
ACM North Central Regional Programming Contest
Problem 1
— Gray Codes
One description of a Gray code (named after xxx) is that it is a sequence of 2k binary numbers, each having k digits, such that adjacent numbers in the sequence differ in only one digit (or bit position). For example, consider the case k = 3. A sequence of eight 3-bit numbers satisfying the requirements is shown in Figure 1, below. Note that the sequence is cyclic, in that the condition that only a single bit is different between adjacent numbers in the sequence is true when considering the last (1 0 0) and the first (0 0 0) numbers in the sequence.
|
0 |
0 |
0 |
|
|
|
|
|
0 |
0 |
0 |
|
0 |
0 |
1 |
|
|
|
|
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
|
|
|
|
0 |
1 |
0 |
|
0 |
1 |
0 |
|
|
|
|
|
0 |
1 |
1 |
|
1 |
1 |
0 |
|
|
|
|
|
1 |
0 |
0 |
|
1 |
1 |
1 |
|
|
|
|
|
1 |
0 |
1 |
|
1 |
0 |
1 |
|
|
|
|
|
1 |
1 |
0 |
|
1 |
0 |
0 |
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Figure 1 |
|
Figure 2 |
|
Figure 3 |
||||||
A classic application of Gray codes is in sensing the position of a drum attached to a rotating mechanical object. Imagine that a strip of paper having k bands (three in this example) is prepared and attached to the drum. Each band is subdivided into 2k colored cells, with a white cell representing a 0 bit in the code, and a black cell representing 1. The three bands for the case k = 3 would appear as shown in Figure 2. Associated with each strip is a light sensor that reports 0 when it senses white, and 1 when it senses black. If the strip is attached to the rotating object, then the sensors report the code (as a 3-bit number) corresponding to the approximate rotational position of the object. Since only one sensor’s output changes at a time during rotation, there is no possibility that imprecise sensor placement will result in an incorrect rotational position report.
Examining Figure 1 we can better understand this physical interpretation of Gray codes. Since there are 8 codes corresponding to 360 degrees of rotation, we see that each code corresponds to a 45-degree region. For example, when the sensors report 000 we know the device is in the 0 to 45 degree region. When the sensors report 010 we know the device is in the 135 to 180 degree region.
Generating the Gray code shown in Figure 1 begins with the binary equivalent of the numbers 0 to 2k-1 (as shown in Figure 3). Now transform each of these numbers by replacing each bit (except the leftmost) by its sum (modulo 2) with the preceding (untransformed) bit. For example, consider the transformation of the number 110. The leftmost bit is unchanged and remains 1. The next bit is replaced by the sum of 1 and 1 (modulo 2), which is 0. The rightmost bit is replaced by the sum of 1 and 0 (modulo 2), which is 1. This yields the value 101, as shown by the corresponding row of the sequence shown in Figure 1.
In this problem you are to display the particular k-bit binary value in a Gray code sequence corresponding to a particular angle A. You will be provided with the values of k and A in the input data. k will be no larger than 32. A will be an integer in the range 0 to 360, and will never correspond to an angle at which the sensors change. For the example given above, A will never be a multiple of 45. Assume that angles increase in the order shown in the example above. The Gray code value containing only zeroes corresponds to the region with the smallest angles.
There will be multiple test cases in the input, each containing integer values for k and A, in that order. A pair of zeroes will follow the last test case.
For each input case, display the case number (these are sequential, starting with 1) and the appropriate k-bit binary value. Separate each bit in the output with a single blank. The output should appear in the same format as shown in the example below.
3 10
3
350
3 91
0 0
1: 0
0 0
2: 1
0 0
3: 0
1 1