SRM572 Div1 Medium

500

前半分と後半分に分けて、半全列挙。
半全列挙なんて最後に使ったのいつだったろう。すっかり存在を忘れていた。

探索でも解けるらしい。rand を使っている人もいた。

class EllysBulls {
public:
  string getNumber(vector <string> g, vector <int> b)
  {
    map<vector<int>, string> h;

    const int left = g.front().size() / 2;
    const int right = g.front().size() - left;

    char buff[10];
    char format[10];
    {
      sprintf(format, "%%0%dd", left);
      const int l = (int)pow(10.0, left);
      for (int i = 0; i < l; ++i) {
        sprintf(buff, format, i);
        vector<int> v;
        for (int j = 0; j < g.size(); ++j) {
          int hit = 0;
          for (int k = 0; k < left; ++k) {
            hit += (g[j][k] == buff[k]);
          }
          v.push_back(hit);
        }
        if (h.count(v)) h[v] = "@";
        else h[v] = string(buff);
      }
    }

    string ret = "";
    const string A = "Ambiguity";
    const string L = "Liar";
    {
      sprintf(format, "%%0%dd", right);
      const int r = (int)pow(10.0, right);
      for (int i = 0; i < r; ++i) {
        sprintf(buff, format, i);
        vector<int> v;
        for (int j = 0; j < g.size(); ++j) {
          int hit = 0;
          for (int k = 0; k < right; ++k) {
            hit += (g[j][left + k] == buff[k]);
          }
          v.push_back(hit);
        }
        vector<int> u;
        for (int j = 0; j < v.size(); ++j) {
          unless (b[j] < v[j]) u.push_back(b[j] - v[j]);
        }
        if (u.size() == v.size()) {
          if (h[u] == "@") return "Ambiguity";
          else {
            if (h[u] != "" && ret != "") return "Ambiguity";
            if (h[u] != "" && ret == "") ret = h[u] + string(buff);
          }
        }
      }
    }
    return ret == "" ? L : ret;
  }
};