【USACO 2.1.5】ヘミングコード

【タイトル説明】

N,B,Dが与えられ、2つの符号化の間に少なくともD単位の「Hamming距離」(1<=D<=7)があるように、N個の0または1からなる符号化(1<=N<=64)が求められる.「Hamming距離」とは、2つの符号化について、それらのバイナリ表現における異なるバイナリビットの数を意味する.以下の2つの符号化0 x 554と0 x 234(0 x 554と0 x 234はそれぞれ2つの16進数を表す)を参照してください.
 

0x554 = 0101 0101 0100

0x234 = 0010 0011 0100

    xxx  xx

5桁が違うので「ハミング距離」は5です.

【様式】

PROGRAM NAME: hamming
INPUT FORMAT:
(file hamming.in)
N,B,Dを含む行.
OUTPUT FORMAT:
(file hamming.out)
N個の符号化(10進数で表す)、並べ替え、10個の1行.解が多ければ、あなたのプログラムはこのような解を出力します:もしそれを2進数にするならば、その値は最小です.

【分析】

直接一つ一つ列挙すればいいです.
注意:Hamming距離は他のすべての数と比較して要求に合致しなければならない.この数は正しい.例えば、サンプル出力、0と7、0と25、0と......の比較はヘミングコードに合致し、同じ7と25、7と30、7と......の比較も要求に合致している.

 1 #include <cstdlib>

 2 #include <iostream>

 3 #include <cstdio>

 4 #include <cstring>

 5 #include <cmath>

 6 #include <queue>

 7 #include <algorithm>

 8 using namespace std;

 9 int ans[70];

10 int N,B,D;

11 int check(int a,int b);

12 int main()

13 {

14     int i,j,point;

15     // 

16     freopen("hamming.in","r",stdin);

17     freopen("hamming.out","w",stdout); 

18     scanf("%d%d%d",&N,&B,&D);

19     ans[1]=0;i=1;point=2;//  

20     while (point!=(N+1))

21     {

22           for (i=i;i<=(1<<B)-1;i++)

23           {

24               for (j=1;j<point;j++) if (check(ans[j],i)<D) goto w;

25               break;// i 

26               w:continue; 

27           }

28           ans[point++]=i;

29     }

30     j=0;

31     for (i=1;i<point;i++) 

32     {

33         j++;

34         if (j==11) {j=1;printf("
");}

35         printf("%d ",ans[i]);

36     } 

37     return 0;

38 }

39 int check(int a,int b)

40 {

41     int cnt=0,i;

42     for (i=0;i<B;i++) if ((a&(1<<i))!=(b&(1<<i))) cnt++;

43     return cnt;

44 }