hamming.cpp

来自「USACO chapter two.Useful for beginners.」· C++ 代码 · 共 77 行

/*
ID: chenkai4
PROG: hamming
LANG: C++
*/
#include <stdio.h>
#include <iostream>
using namespace std;

int N,B,D;int now=1;
int nums[65]={0};

int power2(int n)
{
	int answer=1;
	for(int a=1;a<=n;a++)
		answer*=2;
	return answer;
}

struct _int
{
	int l,b[9];
	_int(int n=0)
	{
		l=0;memset(b,0,sizeof(b));
		while(n)
		{
			b[l++]=n%2;
			n/=2;
			if(b[l])l++;
		}
	}
};

int himindis(int how,int index)
{
	_int i1(how);
	_int i2(nums[index]);
	int answer=0;
	for(int a=0;a<B;a++)
		answer+=(i1.b[a]!=i2.b[a]);
	return answer;
}

bool check(int how)
{
	for(int a=1;a<=now;a++)
		if(himindis(how,a)<D)
			return false;
	return true;
}
int main()
{
	freopen("hamming.in","r",stdin);
	freopen("hamming.out","w",stdout);
	scanf("%d%d%d",&N,&B,&D);
	nums[1]=0;
	for(int a=1;a<=power2(B);a++)
	{
		if(check(a))
			nums[++now]=a;
		if(now==N)
			break;
	}
	for(int a=1;a<=N;a++)
	{
		if((a-1)%10==0)
			printf("%d",nums[a]);
		else
			printf(" %d",nums[a]);
		if(a%10==0||a==N)
			printf("\n");
	}

	return 0;
}