USACO : Hamming Codes


/*
ID: tausiq11
PROG: hamming
LANG: C++
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 100000
#define LL long long

const double EPS = 1e-9;
inline bool Equal(double a, double b) { return abs(a-b) < EPS; }
inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, b) for( int i = 0; i < (b); i++ )
#define Fs(i, x) for( size_t i = 0; i < x.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)
#define Rd(r) freopen(r, "r", stdin)
#define Wt(w) freopen(w, "w", stdout)

using namespace std;

int hammingDistance [255 + 3] [255 + 3];
int n, b, d;
vector <int> output;

void preGenerateValue ()
{
	int cnt;

	for ( int i = 0; i < 256; i++ ) {
		for ( int j = i; j < 256; j++ ) {
			cnt = 0;
			for ( int k = 0; k < 8; k++ ) {
				if ( (i & (1 << k)) ^ (j & (1 << k)) ) cnt++;
			}

			hammingDistance [i] [j] = hammingDistance [j] [i] = cnt;
		}
	}
}

bool findNextNumber (int p)
{
	Fs (i, output) {
		if ( hammingDistance [output [i]] [p] < d ) return false;
	}

	return true;
}

int main ()
{
	Rd ("hamming.in");
	Wt ("hamming.out");

	preGenerateValue ();

	scanf ("%d %d %d", &n, &b, &d);

	output.clear();
	output.push_back(0);

	int num = 1;

	while ( output.size() < n ) {
		while ( !findNextNumber (num) ) num++;
		output.push_back(num);
	}

	Fs (i, output) {
		if ( i % 10 != 0 ) printf (" ");
		printf ("%d", output [i]);
		if ( (i + 1) % 10 == 0 ) printf ("\n");
	}

	if ( output.size() % 10 != 0 ) printf ("\n");

	return 0;
}

// @END_OF_SOURCE_CODE

Judge Response

USER: [tausiq11]
TASK: hamming
LANG: C++

Compiling...
Compile: OK

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

All tests OK.
Your program ('hamming') produced all correct answers!  This is your
submission #3 for this problem.  Congratulations!
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s