首页 > 代码库 > USACO Section 2.1 Hamming Codes

USACO Section 2.1 Hamming Codes

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

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int main()
{
	ifstream infile("hamming.in");
	ofstream outfile("hamming.out");
	if(!infile || !outfile)
	{
		cout << "file operation failure!" << endl;
		return -1;
	}

	int N, B, D;
	infile >> N >> B >> D;
	vector<int> codewords;
	int num = 0;
	codewords.push_back(num);
	while (codewords.size() < N)
	{
		num++;
		int len = codewords.size();
		bool condition = true;
		for (int i=0; i<len; i++)
		{
			int count = 0;
			for (int j=0; j<B; j++)
			{
				int temp = 1 << j;
				if ((temp&num) != (temp&codewords[i]))
				{
					count++;
				}
			}
			if (count < D)
			{
				condition = false;
				break;
			}
		}
		if (condition)
		{
			codewords.push_back(num);
		}
	}

	for (int i=0; i<N; i++)
	{
		if ((i+1)%10 == 0)
		{
			outfile << codewords[i] << endl;
		} else if (i == N-1) {
			outfile << codewords[i];
		} else {
			outfile << codewords[i] << " "; 
		}
	}

	if (N % 10 != 0)
	{
		outfile << endl;
	}

	return 0;
}