Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: mickyta1
- TASK: hamming
- LANG: C++
- */
- #include <bits/stdc++.h>
- using namespace std;
- const int N = (1 << 8) + 5;
- vector<int> chosen;
- int dist[N][N], n, nEx, mnDist;
- int hammingDist(int a, int b){
- int d = a ^ b;
- int cnt = 0;
- for(int e = nEx; e >= 0; --e){
- if(d >= (1 << e)){
- ++cnt;
- d -= 1 << e;
- }
- }
- return cnt;
- }
- void printAns(){
- for(int i = 0; i < (n + 9) / 10; ++i){
- int j;
- for(j = 0; j < 9 && i * 10 + j < n - 1; ++j){
- cout << chosen[i * 10 + j] << ' ';
- }
- cout << chosen[i * 10 + j] << '\n';
- }
- }
- bool recur(int b, int cnt){
- if(cnt == 0){
- printAns();
- return true;
- }
- for(; b < (1 << nEx) - cnt + 1; ++b){
- bool ok = true;
- for(int x : chosen){
- if(dist[x][b] < mnDist){
- ok = false;
- break;
- }
- }
- if(ok){
- chosen.push_back(b);
- if(recur(b, cnt - 1)){
- return true;
- }
- chosen.pop_back();
- }
- }
- return false;
- }
- int main(){
- freopen("hamming.in", "r", stdin);
- freopen("hamming.out", "w", stdout);
- scanf("%d%d%d", &n, &nEx, &mnDist);
- for(int i = 0; i < (1 << nEx) - 1; ++i){
- for(int j = i + 1; j < (1 << nEx); ++j){
- dist[i][j] = hammingDist(i, j);
- }
- }
- recur(0, n);
- fclose(stdin);
- fclose(stdout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement