#include #include #include #include #include using namespace std; struct state{ int rest_percent; int upper_bound; int ix; state(){} state(int rest, int up, int ix) : rest_percent(rest), upper_bound(up), ix(ix){} }; bool operator < (const state &lhs, const state &rhs) { return make_pair(lhs.rest_percent, make_pair(lhs.upper_bound, lhs.ix)) < make_pair(rhs.rest_percent, make_pair(rhs.upper_bound, rhs.ix)); } struct part{ string name; int atmost, atleast; int percent; part(): atmost(-1), atleast(101), percent(-1){} }; bool solve(vector &parts, map &dptable, int ix, int rest, int upper) { if(dptable.count(state(rest, upper, ix))) return dptable[state(rest, upper, ix)]; bool ret; if(ix >= parts.size()){ // over last element ret = (rest == 0); }else{ part &me = parts[ix]; vector tryval; if(me.percent == -1){ for(int i = 1; i <= 100; ++i) tryval.push_back(i); }else{ tryval.push_back(me.percent); } ret = false; for(int i = 0; i < tryval.size(); ++i){ if(tryval[i] > rest || tryval[i] > upper) continue; bool r = solve(parts, dptable, ix+1, rest - tryval[i], tryval[i]); if(r){ ret = true; me.atmost = max(me.atmost, tryval[i]); me.atleast = min(me.atleast, tryval[i]); } } } return dptable[state(rest, upper, ix)] = ret; } int main(void) { ifstream cin("declaration.in"); int N; while(cin >> N && N){ vector prod_names; vector > products; for(int i = 0; i < N; ++i){ string prod; cin >> prod; prod_names.push_back(prod); vector eachprod; int nc; cin >> nc; for(int j = 0; j < nc; ++j){ string line; part p; cin >> ws; getline(cin, line); istringstream is(line); // no problem even though percent does not exist is >> p.name >> p.percent; eachprod.push_back(p); } map dptable; solve(eachprod, dptable, 0, 100, 100); /* for(int j = 0; j < eachprod.size(); ++j){ cout << eachprod[j].name << " has " << eachprod[j].atmost << "-" << eachprod[j].atleast << endl; } */ products.push_back(eachprod); } int Q; cin >> Q; for(int i = 0; i < Q; ++i){ string order, target; cin >> order >> target; vector > results(2); for(int j = 0; j < products.size(); ++j){ vector &theprod = products[j]; bool notfound = true; for(int k = 0; k < theprod.size(); ++k){ if(theprod[k].name == target){ notfound = false; results[0].push_back(theprod[k].atmost); results[1].push_back(theprod[k].atleast); break; } } if(notfound) { results[0].push_back(0); results[1].push_back(0); } } vector res; if(order == "most"){ int maxmin = *max_element(results[1].begin(), results[1].end()); for(int j = 0; j < prod_names.size(); ++j){ if(results[0][j] >= maxmin){ res.push_back(prod_names[j]); } } }else{ int minmax = *min_element(results[0].begin(), results[0].end()); for(int j = 0; j < prod_names.size(); ++j){ if(results[1][j] <= minmax){ res.push_back(prod_names[j]); } } } for(int j = 0; j < res.size(); ++j){ if(j != 0) cout << " "; cout << res[j]; } cout << endl; } } return 0; }