GCJ2015_2C.cc

#include <unordered_map>
#include <iostream>
#include <cstring>
#include <sstream>

#define MAXW 2300
using namespace std;

int n;
unordered_map<string, int> mid;
int W[MAXW], sz;
int getId(const string &s) {
  unordered_map<string, int>::iterator it = mid.find(s);
  if (it != mid.end())
    return it->second;
  mid[s] = sz++;
}

inline bool isBoth(int mask, int i) {
  return (W[i] & mask) && (W[i] & ~mask);
}

int localAns[1<<18];

int solve() {
  mid.clear();
  memset(W, 0, sizeof W);
  sz = 0;
  cin >> n;
  string s;
  getline(cin, s);
  for (int i = 0; i < n; ++i) {
    getline(cin, s);
    stringstream ss(s);
    while (ss >> s)
      W[getId(s)] |= (1 << i);
  }
  int q = 1 << (n-2);
  for (int m = 0; m < q; ++m) {
    int mask = (m << 2) | 2, cnt = 0;
    for (int i = 0; i < sz; ++i)
      if (isBoth(mask, i))
        ++cnt;
    localAns[m] = cnt;
  }
  int ans = localAns[0];
  for (int i = 1; i < q; ++i)
    ans = min(ans, localAns[i]);
  return ans;
}

int main() {
  ios::sync_with_stdio(0);
  int tc;
  cin >> tc;
  for (int cs = 1; cs <= tc; ++cs) {
    cout << "Case #" << cs << ": ";
    cout << solve();
    cout << endl;
  }
  return 0;
}