#include #include #include #include #include #include #include #include #include using namespace std; const int inf = 1<<29; const char male_list[] = "mFsHB"; const char female_list[] = "fMdWS"; const int dist_list[] = { 0, 1, 1, 0, 2 }; bool male[256]; int dist[256]; map > dic; char rule[256][256]; enum SpecialRule { None = 0, Fail, Male, Female, HorMale, WorFemale, BandMale, SandFemale, }; void Init() { for (int i = 0; male_list[i]; ++i) { male[male_list[i]] = true; dist[male_list[i]] = dist[female_list[i]] = dist_list[i]; } dic["A"].push_back("m"); dic["A"].push_back("f"); dic["father"].push_back("F"); dic["mother"].push_back("M"); dic["son"].push_back("s"); dic["daughter"].push_back("d"); dic["husband"].push_back("H"); dic["wife"].push_back("W"); dic["brother"].push_back("B"); dic["sister"].push_back("S"); dic["uncle"].push_back("FB"); dic["uncle"].push_back("MB"); dic["aunt"].push_back("FS"); dic["aunt"].push_back("MS"); dic["nephew"].push_back("Bs"); dic["nephew"].push_back("Ss"); dic["niece"].push_back("Bd"); dic["niece"].push_back("Sd"); dic["grandfather"].push_back("FF"); dic["grandfather"].push_back("MF"); dic["grandmother"].push_back("FM"); dic["grandmother"].push_back("MM"); dic["grandson"].push_back("ss"); dic["grandson"].push_back("ds"); dic["granddaughter"].push_back("sd"); dic["granddaughter"].push_back("dd"); rule['m']['H'] = Fail; rule['f']['W'] = Fail; rule['F']['s'] = BandMale; rule['F']['d'] = SandFemale; rule['F']['H'] = Fail; rule['F']['W'] = 'M'; rule['M']['s'] = BandMale; rule['M']['d'] = SandFemale; rule['M']['H'] = 'F'; rule['M']['W'] = Fail; rule['s']['F'] = HorMale; rule['s']['M'] = WorFemale; rule['s']['H'] = Fail; rule['s']['B'] = 's'; rule['s']['S'] = 'd'; rule['d']['F'] = HorMale; rule['d']['M'] = WorFemale; rule['d']['W'] = Fail; rule['d']['B'] = 's'; rule['d']['S'] = 'd'; rule['H']['s'] = 's'; rule['H']['d'] = 'd'; rule['H']['H'] = Fail; rule['H']['W'] = Female; rule['W']['s'] = 's'; rule['W']['d'] = 'd'; rule['W']['H'] = Male; rule['W']['W'] = Fail; rule['B']['F'] = 'F'; rule['B']['M'] = 'M'; rule['B']['B'] = BandMale; rule['B']['S'] = SandFemale; rule['S']['F'] = 'F'; rule['S']['M'] = 'M'; rule['S']['B'] = BandMale; rule['S']['S'] = SandFemale; } int ans_m, ans_M, debug_total; vector input; string seq; // In fact, cache isn't required. set > cache; inline string StringReplaced(const string& str, int i, char c) { string copy(str); copy[i] = c; return copy; } void GetDist(int p, const string& cur) { if (!cache.insert(make_pair(p, cur)).second) return; if (p == (int)seq.size()) { int d = 0; for (int i = 0; i < (int)cur.size(); ++i) d += dist[cur[i]]; ans_m = min(ans_m, d); ans_M = max(ans_M, d); return; } int i = cur.size() - 1; char r = rule[cur[i]][seq[p]]; switch(r) { case None: GetDist(p + 1, cur + seq[p]); break; case Fail: break; case Male: if (male[cur[i-1]]) GetDist(p + 1, cur.substr(0, i)); break; case Female: if (!male[cur[i-1]]) GetDist(p + 1, cur.substr(0, i)); break; case HorMale: if (male[cur[i-1]]) GetDist(p + 1, cur.substr(0, i)); else GetDist(p + 1, StringReplaced(cur, i, 'H')); break; case WorFemale: if (!male[cur[i-1]]) GetDist(p + 1, cur.substr(0, i)); else GetDist(p + 1, StringReplaced(cur, i, 'W')); break; case BandMale: if (male[cur[i-1]]) GetDist(p + 1, cur.substr(0, i)); GetDist(p + 1, StringReplaced(cur, i, 'B')); break; case SandFemale: if (!male[cur[i-1]]) GetDist(p + 1, cur.substr(0, i)); GetDist(p + 1, StringReplaced(cur, i, 'S')); break; default: GetDist(p + 1, StringReplaced(cur, i, r)); } } void GetDistance(const string& str) { seq = str; cache.clear(); GetDist(1, str.substr(0, 1)); debug_total += cache.size(); } void MakeSeq(int p, const string& str) { if (p == (int)input.size()) { GetDistance(str); return; } const vector& cand = dic[input[p]]; assert(!cand.empty()); for (int i = 0; i < (int)cand.size(); ++i) MakeSeq(p + 1, str + cand[i]); } int main() { ifstream cin("I.txt"); Init(); int nnn; cin >> nnn >> ws; string line; for (int iii = 0; iii < nnn; ++iii) { getline(cin, line); input.clear(); istringstream iss(line); string str_C, str_is, word; iss >> str_C >> str_is; assert(str_C == "C" && str_is == "is"); while (true) { iss >> word; if (word.size() < 2 || word.substr(word.size() - 2) != "'s") { input.push_back(word); break; } input.push_back(word.substr(0, word.size() - 2)); } ans_m = inf; ans_M = -1; debug_total = 0; MakeSeq(0, ""); cout << ans_M << " " << ans_m << /*" " << debug_total <<*/ endl; } }