2014-07-24

UVa 11663 - GrayInc

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

Gray Inc. is a software fabricant specialized in management of Gray codes. An n-binary code, for n $\geq$ 1, is a sequence of words w0, w1,… that includes every possible binary word of n bits. An n-Gray code is an n-binary code such that between any two consecutive words there is only one bit that changes, i.e., they differ at exactly one position. As you might be aware by now, there are many n-Gray codes.

Gray Inc. produces its own particular kind of Gray code in the following way (name Gn the produced n-Gray code, n $\geq$ 1):

$$Gn = \left\{\vphantom{ \begin{array}{lr} \langle 0 , 1 \rangle & \... ... (0G_{n-1}) \, (1G_{n-1}^R) & \textrm{if } n \geq 2 \\ \end{array} }\right. \begin{array}{lr} \langle 0 , 1 \rangle & \textrm{if } n = 1\\ & \\ (0G_{n-1}) \, (1G_{n-1}^R) & \textrm{if } n \geq 2 \\ \end{array}$$

The notation defining Gn should be understood as follows:

$bA$ : appends bit b to every element of the sequence A;
$AB$ : concatenates sequences A and B;
$A^{R}$ : sequence with the elements of sequence A in reversed order.

For instance,

G2 = (0G1) (1G1R)
= (0$\displaystyle \langle$0, 1$\displaystyle \rangle$) (1$\displaystyle \langle$0, 1$\displaystyle \rangle^_{}$)
= (0$\displaystyle \langle$0, 1$\displaystyle \rangle$) (1$\displaystyle \langle$1, 0$\displaystyle \rangle$)
= $\displaystyle \langle$00, 01$\displaystyle \rangle$$\displaystyle \langle$11, 10$\displaystyle \rangle$

=    {% math %}\displaystyle \langle{% endmath %}00, 01, 11, 10{% math %}\displaystyle \rangle{% endmath %}

and

G3 = (0G2) (1G2R)
= (0$\displaystyle \langle$00, 01, 11, 10$\displaystyle \rangle$) (1$\displaystyle \langle$00, 01, 11, 10$\displaystyle \rangle^_{}$)
= (0$\displaystyle \langle$00, 01, 11, 10$\displaystyle \rangle$) (1$\displaystyle \langle$10, 11, 01, 00$\displaystyle \rangle$)
= $\displaystyle \langle$000, 001, 011, 010$\displaystyle \rangle$$\displaystyle \langle$110, 111, 101, 100$\displaystyle \rangle$
= $\displaystyle \langle$000, 001, 011, 010, 110, 111, 101, 100$\displaystyle \rangle$

Observe that not only Gn is an n-Gray code, but also a circular Gray code as the first word in the sequence may be regarded as the successor of the last one in the sequence.

Gray Inc. wants your help to solve the following problem: given a binary word w in Gn and a natural number m, they want to produce the binary word in the sequence Gn that is m words ahead w in the listing (of course, considering the circular ordering described above). Can you help them?

Input

The problem input consists of several cases, each one defined by a line with an integer m ( 0 < m $\leq$ 1000), and a binary n-word w ( 1 $\leq$ n $\leq$ 100), separated by one blank.

The end of the input is given by a line with m = 0 and w = 0.

Output

For each input case, your solution should output the n-binary word that is m words ahead of w in the listing of Gn.

Sample Input

1 0
3 0
1 1
1 11
6 011
123 010101010
0 0

Sample Output

Solution

題目描述：

根據格雷碼的產生方式，找到某個格雷碼的下 m (m < 1000) 個格雷碼為何。

題目解法：

由於給定的格雷碼長度可能太長，因此如果要用數學解的話必須搭配大數處理，然而 m 就相對於小，因此直接使用原本的格雷碼窮舉方式，針對給定的格雷碼進行還原操作，還原結束後，開始計數直到指定的格雷碼。

#include <stdio.h> 
#include <string.h>
//#define DEBUG
int gray(int n, int k) { // find k-th gray code
    if(n == 0)  return 0;
    if(k >= (1<<(n-1)))
        return (1<<(n-1)) | gray(n-1, (1<<(n))-k-1);
    else
        return gray(n-1, k);
}
int path[128];
void grayNext(int idx, int n, char w[], int& k, int &f) {
    if(f == 2)	return;
    if(idx == n) {
        if(f == 0) {
            f = 1;
        } else {
            k--;
            if(k == 0) {
                for(int i = 0; i < n; i++)
                    printf("%d", path[i]);
                puts("");
                f = 2;
            }
        }
#ifdef DEBUG
        for(int i = 0; i < n; i++)
            printf("%d", path[i]);
        puts("");
#endif
        return ;
    }
    if(f == 0) {
        if(w[idx] == path[idx] + '0') {
            grayNext(idx+1, n, w, k, f);
            path[idx] = !path[idx];
            grayNext(idx+1, n, w, k, f);
        } else {
            for(int i = idx; i < n; i++)
                path[i] = 0;
            path[idx] = w[idx] - '0';path[idx+1] = 1;
            grayNext(idx+1, n, w, k, f);
        }
    } else {
        grayNext(idx+1, n, w, k, f);
        path[idx] = !path[idx];
        grayNext(idx+1, n, w, k, f);
    }
    
}
int main() {
    int n, m, f;
    char w[1024];
    while(scanf("%d %s", &n, w) == 2 && n) {
        f = 0;
        memset(path, 0, sizeof(path));
        m = strlen(w);
//		printf("find next %d\n", n);
        grayNext(0, m, w, n, f);
        while(n) {
            memset(path, 0, sizeof(path));
            grayNext(0, m, w, n, f);
        }
    }
    return 0;
}

Morris' Blog