USACO section 2.1 Hamming Codes(直接枚举暴搜)

Hamming Codes
Rob Kolstad

Given N, B, and D: Find a set of N codewords (1

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

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

PROGRAM NAME: hamming

INPUT FORMAT

N, B, D on a single line

SAMPLE INPUT (file hamming.in)

16 7 3

OUTPUT FORMAT

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.

SAMPLE OUTPUT (file hamming.out)

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

刚拿到题还不知道怎办，有想过暴搜，但怕暴，百度了下，发现真可以暴搜，就直接搜了明显是数据太弱了，

要是输入 126 30 6 就很久没反应了。

/*
ID:nealgav1
PROG:hamming
LANG:C++
*/
#include
using namespace std;
const int mm=10)
  {
    if(z&1)
    ans++;
    z>>=1;
  }
  return ans;
}
void dfs(int dep)
{
  if(dep==a)return;
  int i,j;
  for(i=1;i>a>>b>>c;
  len=1

Hamming Codes
Brian Jacokes

There are only a few tools we need to solve this problem. First of all, we can use basic techniques to find the Nth bit of a number M: counting the least significant bit as bit 0, the next bit as bit 1, etc., we can find the value of that bit through the expression

int Nth_bit = (1

In other words, we are shifting the number 1 left by N spaces, and then performing a binary AND on the resulting number with our original number, which will leave either a 1 in the Nth bit or a 0. So the first thing we have to do is find out the distance between each pair of numbers within the set of all numbers with B bits (0..2^B-1).

We also know that 0 can be one of the numbers in the set, because if the minimum number in the set were N instead of 0, we could XOR N to each number in the set and they would still be the same distance apart. The limits on the problem are low enough that we can do a DFS, and as soon as we hit a solution we can output it and exit.

#include 
#include 
#include 
#define MAX (1 

USER: Neal Gavin Gavin [nealgav1]
TASK: hamming
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3336 KB]
   Test 2: TEST OK [0.011 secs, 3336 KB]
   Test 3: TEST OK [0.000 secs, 3336 KB]
   Test 4: TEST OK [0.000 secs, 3336 KB]
   Test 5: TEST OK [0.000 secs, 3336 KB]
   Test 6: TEST OK [0.000 secs, 3336 KB]
   Test 7: TEST OK [0.000 secs, 3336 KB]
   Test 8: TEST OK [0.000 secs, 3336 KB]
   Test 9: TEST OK [0.000 secs, 3336 KB]
   Test 10: TEST OK [0.000 secs, 3336 KB]
   Test 11: TEST OK [0.000 secs, 3336 KB]

All tests OK.

Your program (‘hamming’) produced all correct answers! This is your
submission #2 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 ----
16 7 3
------- test 2 ----
2 7 7
------- test 3 ----
3 6 4
------- test 4 ----
5 5 1
------- test 5 ----
10 8 4
------- test 6 ----
20 6 2
------- test 7 ----
32 5 1
------- test 8 ----
50 8 2
------- test 9 ----
60 7 2
------- test 10 ----
16 8 3
------- test 11 ----
15 8 4

Keep up the good work!

Thanks for your submission!

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 最新React技术栈，实战复杂低代码项目-仿问卷星完结江山也要伟人扶

download：最新React技术栈，实战复杂低代码项目-仿问卷星完结 ChatGPT：开启人机交互新时代的AI语言模型 在现代科技快速发展的今天，人工智能已经成为了一个备受关注的话题，而ChatGPT作为一种基于自然语言处理技术的AI语言模型，在人机交互方…