mickypinata

USACO-T025: Hamming Codes

Nov 30th, 2021
642
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: hamming
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = (1 << 8) + 5;
  11.  
  12. vector<int> chosen;
  13. int dist[N][N], n, nEx, mnDist;
  14.  
  15. int hammingDist(int a, int b){
  16.     int d = a ^ b;
  17.     int cnt = 0;
  18.     for(int e = nEx; e >= 0; --e){
  19.         if(d >= (1 << e)){
  20.             ++cnt;
  21.             d -= 1 << e;
  22.         }
  23.     }
  24.     return cnt;
  25. }
  26.  
  27. void printAns(){
  28.     for(int i = 0; i < (n + 9) / 10; ++i){
  29.         int j;
  30.         for(j = 0; j < 9 && i * 10 + j < n - 1; ++j){
  31.             cout << chosen[i * 10 + j] << ' ';
  32.         }
  33.         cout << chosen[i * 10 + j] << '\n';
  34.     }
  35. }
  36.  
  37. bool recur(int b, int cnt){
  38.     if(cnt == 0){
  39.         printAns();
  40.         return true;
  41.     }
  42.     for(; b < (1 << nEx) - cnt + 1; ++b){
  43.         bool ok = true;
  44.         for(int x : chosen){
  45.             if(dist[x][b] < mnDist){
  46.                 ok = false;
  47.                 break;
  48.             }
  49.         }
  50.         if(ok){
  51.             chosen.push_back(b);
  52.             if(recur(b, cnt - 1)){
  53.                 return true;
  54.             }
  55.             chosen.pop_back();
  56.         }
  57.     }
  58.     return false;
  59. }
  60.  
  61. int main(){
  62.     freopen("hamming.in", "r", stdin);
  63.     freopen("hamming.out", "w", stdout);
  64.  
  65.     scanf("%d%d%d", &n, &nEx, &mnDist);
  66.     for(int i = 0; i < (1 << nEx) - 1; ++i){
  67.         for(int j = i + 1; j < (1 << nEx); ++j){
  68.             dist[i][j] = hammingDist(i, j);
  69.         }
  70.     }
  71.     recur(0, n);
  72.  
  73.     fclose(stdin);
  74.     fclose(stdout);
  75.     return 0;
  76. }
  77.  
RAW Paste Data