Problem 2.1.7 Hamming Codes

출처: https://train.usaco.org/usacogate

---

문제 설명

Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8),
such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each
of the other codewords.

입력

N, B, D on a single line

출력

N codewords, sorted, in decimal, ten per line.

입력 예

16 7 3

출력 예

0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

---

문제 풀이

Hamming Distance 계산하는 방법에 대한 문제이다. 각각의 bit 값을 비교하기 위해서, 2로 계속 나누고 달라질때마다 distance를 증가시키는 방법으로 계산한다. 0 부터 숫자를 키워가면서 distance > D인 경우들을 계속 추가시켜서 기록하고, 출력할때 10개 단위로 출력한다.

프로그램 내용

int getHammingDistance(int a, int b)
{
    int ret=0;

    while( a> 0 || b>0)
    {
        if( a%2 != b%2)
            ret++;
        a /= 2;
        b /= 2;
    }
    return ret;
};

...

  ans.push_back(0);
    /// check hamming distance > D, put result
    for(int i=0;i < maxB ;i++)
    {
        bool ok= true;

        /// compare hamming distance with last code
        for(int j=0;j!=ans.size();j++)
        {
            /// distance < D
            if( getHammingDistance(i,ans[j]) < D )
            {
                ok = false;
                break;
            }
        }
        /// distance >= D
        if(ok)
        {
            ans.push_back(i);
        }

        /// Max output number
        if(ans.size() >= N)
        {
                break;
        }
    }

 

Chapter 2. Bigger Challenges ( link )