contest3.D.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <set>
#include <map>

using namespace std;

map<string, string> phena, phenb;

typedef map<string, string>::const_iterator iter;

vector<pair<string, string> > match(string ph) {
  vector<pair<string, string> > result;
  for(iter ita = phena.begin(); ita != phena.end(); ita++) {
    for(iter itb = phenb.begin(); itb != phenb.end(); itb++) {
      if(ph == "?" || ita->second + itb->second == ph) {
        result.push_back(make_pair(ita->first, itb->first));
      }
    }
  }
  return result;
}

bool yields(string A, string B, string C) {
  for(int i = 0; i < 2; i++) {
    for(int j = 0; j < 2; j++) {
      for(int k = 0; k < 2; k++) {
        if (C[k] == A[i] && C[1 - k] == B[j]) {
          return true;
        }
      }
    }
  }
  return false;
}

void output(set<string>& pp) {
  if(pp.empty()) {
    cout << " IMPOSSIBLE";
  } else if(pp.size() == 1) {
    cout << ' ' << *pp.begin();
  } else {
    cout << " {";
    for(set<string>::const_iterator it = pp.begin(); it != pp.end(); it++) {
      if (it != pp.begin()) cout << ", ";
      cout << *it;
    }
    cout << "}";
  }
}

int main() {
  phena["AA"] = "A";
  phena["AB"] = phena["BA"] = "AB";
  phena["AO"] = phena["OA"] = "A";
  phena["BB"] = "B";
  phena["BO"] = phena["OB"] = "B";
  phena["OO"] = "O";

  phenb["--"] = "-";
  phenb["-+"] = "+";
  phenb["+-"] = "+";
  phenb["++"] = "+";

  for(int t = 1; ; t++) {
    string A, B, C;
    cin >> A >> B >> C;
    if(A == "E") {
      break;
    }

    vector<pair<string, string> > ap = match(A);
    vector<pair<string, string> > bp = match(B);
    vector<pair<string, string> > cp = match(C);
    set<string> ppa, ppb, ppc;
    if (A != "?") ppa.insert(A);
    if (B != "?") ppb.insert(B);
    if (C != "?") ppc.insert(C);
    for(int i = 0; i < ap.size(); i++) {
      for(int j = 0; j < bp.size(); j++) {
        for(int k = 0; k < cp.size(); k++) {
          if(yields(ap[i].first, bp[j].first, cp[k].first) &&
             yields(ap[i].second, bp[j].second, cp[k].second)) {
            ppa.insert(phena[ap[i].first] + phenb[ap[i].second]);
            ppb.insert(phena[bp[j].first] + phenb[bp[j].second]);
            ppc.insert(phena[cp[k].first] + phenb[cp[k].second]);
          }
        }
      }
    }

    cout << "Case " << t << ":";
    output(ppa);
    output(ppb);
    output(ppc);
    cout << '\n';
  }
  return 0;
}