uva-1252

#include <iostream> #include <vector> #include <stack> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <cstring> #include <unordered_map> #include <unordered_set> #include <algorithm> #include <numeric> #include <chrono> #include <ctime> #include <cmath> #include <cctype> #include <string> #include <cstdio> #include <iomanip> #include <thread> #include <mutex> #include <condition_variable> #include <functional> #include <iterator> using namespace std; const int MAXSIZE = 4096,INF = 0x3f3f3f3f; int n, m; char buf[32]; int d[MAXSIZE][MAXSIZE] = { 0 }, goods[256] = {0},nCount = 0; int dp(int s, int a) { if (d[s][a] != INF) return d[s][a]; int t = 0; for (int i = 0; i < n; ++i) { if ((goods[i] & s) == a) ++t; } if (t <= 1) { d[s][a] = 0; return 0; } for (int i = 0; i <= m; ++i) { t = 1 << i; if(s & t) continue; d[s][a] = min(d[s][a],max(dp(s | t, a | t), dp(s | t, a) ) + 1); } return d[s][a]; } int GetFlag() { int ret = 0; for (int i = 0; i < m; ++i) { ret = ret << 1; if (buf[i] == '1') ret |= 1; } return ret; } int main() { while (cin >> m >> n && m && n) { cin.get(); nCount = 0; memset(d, 0x3f, sizeof(d)); for (int i = 1; i <= n; ++i) { fgets(buf, 32, stdin); goods[nCount++] = GetFlag(); } cout << dp(0, 0) << endl; } return 0; }