USACO-Section 2.1 Hamming Codes (DFS)
説明
N,B,Dが与えられる:N個の符号化(1<=N<=64)が見出され、各符号化はBビット[バイナリ](1<=B<=8)であり、両符号化間に少なくともD単位の「ヘミング距離」(1<=D<=7)がある.「ヘミング距離」とは、2つの符号化について、それらのバイナリ表現における異なるバイナリビットの数を指す.次の2つの符号化0 x 554と0 x 234の違いを見てください(0 x 554は16進数を表し、各ビットはそれぞれ5,5,4です).
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進数にするならば、その値は最小です.
SAMPLE INPUT
16 7 3
SAMPLE OUTPUT
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127
0は最小の数であるため、0は必ずあり、DFSで検索すればよい.小さい頃から大きな列挙であるため、見つけた最初の答えはテーマが求めた答えである.
/*
ID: your_id_here
PROG: hamming
LANG: C++
*/
#include <cstdio>
#include <cstring>
using namespace std;
int n,b,d,ans[65],num,ready[255],rn,t,tt,tmp,mx;
bool isLegal(int x,int y) {
x^=y,tmp=0;
for(t=0;t<b;++t)
if(x&(1<<t))
++tmp;
return tmp>=d;
}
inline bool choose(int index) {
for(tt=1;tt<num;++tt)// , , ,
if(!isLegal(ans[tt],ready[index]))
return false;
return true;
}
bool dfs(int index) {
if(num==n)//
return true;
do {
while(index<rn&&!choose(index))
++index;
if(index==rn) {// , -1
--num;
return false;
}
ans[num++]=ready[index++];
if(dfs(index))
return true;
}while(index<rn);
--num;// , -1
return false;
}
int main() {
int i;
freopen("hamming.in","r",stdin);
freopen("hamming.out","w",stdout);
while(3==scanf("%d%d%d",&n,&b,&d)) {
ans[0]=rn=0,num=1,mx=1<<b;
for(i=1;i<mx;++i)
if(isLegal(0,i))
ready[rn++]=i;
dfs(0);
for(--num,i=0;i<=num;++i)
printf("%d%c",ans[i],(i+1)%10==0||i==num?'
':' ');
}
return 0;
}