USACO chapter 2 section 2.1 Hamming Codes

USER: tianbing tianbing [tbbd4261]
TASK: hamming
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.

Your program ('hamming') produced all correct answers!  This is your
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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


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

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜