同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

10132_HammingCodes

2022-5-16 18:16| 发布者: Hocassian| 查看: 96| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504583467299-Problem List-采集的数据-后羿采集器.html

Pro.ID

10132

Title

Hamming Codes

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10132

AC

Submit

Ratio

35.71%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

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. 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):

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
Bit differences: xxx xx

Since five bits were different, the Hamming distance is 5.

输入

Multiple test case. For each case:

N, B, D on a single line.

输出

Description

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
Bit differences: xxx xx

Since five bits were different, the Hamming distance is 5.

Input

Multiple test case. For each case:

N, B, D on a single line.

Output

For each case, output 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.

Output a blank line after each case.

Sample Input

16 7 3
2 7 7

Sample Output

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

0 127

Source

USACO training course