USACO chapter 2 section 2.1 Hamming Codes

USER: tianbing tianbing [tbbd4261]
LANG: C++

Compiling...
Compile: OK

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

All tests OK.

submission #5 for this problem.  Congratulations!

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

#include<iostream>
#include<fstream>
#include<climits>
#include<cstring>
using namespace std;

ifstream fin("hamming.in");
ofstream fout("hamming.out");

int N,B,D,len=0;
int ans[65]={0};

bool ishammingCoding(int a, int b)
{
int temp=a^b,cnt=0;
while(temp>0)
{
if(temp%2)cnt++;
temp/=2;
}
return cnt>=D;
}

void solve()
{
ans[1]=0;   len=1;
for(int i=1; i<(1<<B); i++)
{
bool okay=1;
for(int j=1; j<=len; j++)
if(!ishammingCoding(i,ans[j]))
okay=0;
if(okay)
{
ans[++len]=i;
}

if(len==N)break;
}

for(int i=1; i<=N; i++)
{
if(i%10==1)fout<<ans[i];
else fout<<' '<<ans[i];
if(i%10==0||i==len)fout<<endl;
}

}
int main()
{

fin>>N>>B>>D;
solve();

//system("pause");
return 0;
}

posted on 2010-06-22 11:53 田兵 阅读(59) 评论(0)  编辑 收藏 引用 所属分类: USACO

 < 2010年6月 >
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

• 随笔 - 65
• 文章 - 2
• 评论 - 17
• 引用 - 0

•

• 积分 - 23605
• 排名 - 667