Pedometer

gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <set>

using namespace std;

#define FOREDGE(adj, it, v) for (EdgeList::iterator it = adj[v].begin();\
    it != adj[v].end(); ++it)

typedef pair<int, int> ii;
typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;
typedef unsigned long long ullong;

int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  setvbuf(stdout, NULL, _IOFBF, 10000);
 
  int n_cases;
  scanf("%d", &n_cases);
  int arr[128];
  for (int ctr = 0; ctr < n_cases; ++ctr) {
    int p, n;
    scanf("%d%d", &p, &n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < p; ++j) {
        int b;
        scanf("%d", &b);
        arr[i] = (arr[i] << 1) | b;
      }
    }
    int minim = 1 << 30;
    set<int> set;
    for (int i = 0; i < (1 << p); ++i) {
      int n_on = __builtin_popcount(i);
      if (n_on >= minim) break;
      set.clear();
      bool good = true;
      for (int j = 0; j < n; ++j) {
        int x = arr[j] & i;
        if (set.count(x) > 0) {
          good = false;
          break;
        }
        set.insert(x);
      }
      if (good) minim = n_on;
    }
    printf("%d\n", max(minim, 1));
  }

  return 0;
}