hamming.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:hamming
}

program hamming;
const
  maxn=64;
var
  fin,fout:text;
  dist:array[0..255,0..255]of byte;
  code:array[1..maxn]of byte;
  n,b,d,max,i,j:byte;
function hamdist(x,y:byte):byte;
  var
    i:byte;
  begin
    hamdist:=0;
    for i:=1 to b do begin
      if odd(x) xor odd(y) then inc(hamdist);
      x:=x div 2;y:=y div 2;
    end;
  end;
procedure out;
  var
    i:byte;
  begin
    assign(fout,'hamming.out');
    rewrite(fout);
    for i:=1 to n-1 do begin
      write(fout,code[i]);
      if i mod 10=0 then writeln(fout) else write(fout,' ');
    end;
    writeln(fout,code[n]);
    close(fout);
    halt;
  end;
procedure search(l,s:byte);
  var
    i,j:byte;
    ok:boolean;
  begin
    for i:=s to max-n+l do begin
      ok:=true;
      for j:=1 to l-1 do
        if dist[code[j],i]<d then begin
          ok:=false;
          break;
        end;
      if not ok then continue;
      code[l]:=i;
      if l=n then out else search(l+1,i+1);
    end;
  end;
begin
  assign(fin,'hamming.in');
  reset(fin);
  readln(fin,n,b,d);
  close(fin);

  max:=power(2,b)-1;
  for i:=0 to max do
    for j:=0 to max do
      if i<j then
        dist[i,j]:=hamdist(i,j)
      else if i=j then
        dist[i,j]:=0
      else
        dist[i,j]:=dist[j,i];

  search(1,0);
end.