P1461 [USACO2.1] Hamming Codes

Given $N$, $B$, and $D$, find a set of $N$ codewords ($1 \le N \le 64$), each of length $B$ bits ($1 \le B \le 8$), such that each of the codewords is at least Hamming distance $D$ ($1 \le D \le 7$) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords `0x554` and `0x234` and their differences. `0x554` means the hexadecimal number with hex digits $5$, $5$, and $4$, and a hex digit requires four bits: ``` 0x554 = 0101 0101 0100 0x234 = 0010 0011 0100 Bit differences: -XXX -XX- ---- ``` Since five bits were different, the Hamming distance is $5$.

$N$, $B$, $D$ on a single line.

$N$ codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted as a base $2^B$ integer, would have the least value.

USACO Training Section 2.1