#include #include #include #include using namespace std; struct ingredient_t { string name; int exact; int max, min; ingredient_t(string _name, int _exact) : max(0), min(100), name(_name), exact(_exact) {} }; struct product_t { string name; vector ingredients; }; // depth left_percentage prev_percentage int table[ 100][ 101][ 101]; bool recursive(vector &ingredients, int depth, int left_percentage, int prev_percentage); bool assign_percentage(vector &ingredients, int depth, int left_percentage, int prev_percentage, int this_percentage) { if (left_percentage >= this_percentage && prev_percentage >= this_percentage) { if (recursive(ingredients, depth+1, left_percentage - this_percentage, this_percentage)) { if (ingredients[depth].max < this_percentage) { ingredients[depth].max = this_percentage; } if (ingredients[depth].min > this_percentage) { ingredients[depth].min = this_percentage; } return true; } } return false; } bool recursive(vector &ingredients, int depth, int left_percentage, int prev_percentage) { if (depth >= ingredients.size()) { return left_percentage == 0; } if (table[depth][left_percentage][prev_percentage] >= 0) { return table[depth][left_percentage][prev_percentage] == 1; } bool found = false; if (ingredients[depth].exact >= 0) { // exact percentage is given. found = assign_percentage(ingredients, depth, left_percentage, prev_percentage, ingredients[depth].exact); } else { // 1 - 100% for (int p = 1; p <= 100; p++) { if (assign_percentage(ingredients, depth, left_percentage, prev_percentage, p)) { found = true; } } } table[depth][left_percentage][prev_percentage] = found ? 1 : 0; return found; } int main() { int P; while (cin >> P && P > 0) { product_t p[10]; for (int i = 0; i < P; i++) { string s; int n; cin >> p[i].name; cin >> n; getline(cin, s); // skip a newline for (int j = 0; j < n; j++) { getline(cin, s); istringstream iss(s); string name; int exact; if (!(iss >> name >> exact)) { exact = -1; } p[i].ingredients.push_back(ingredient_t(name, exact)); } } for (int i = 0; i < P; i++) { // initializing cache for (int j = 0; j < 100; j++) { for (int k = 0; k < 101; k++) { for (int l = 0; l < 101; l++) { table[j][k][l] = -1; } } } recursive(p[i].ingredients, 0, 100, 100); } int Q; cin >> Q; for (int q = 0; q < Q; q++) { string word, target_ingredient; cin >> word >> target_ingredient; int min_max = 101, max_min = -1; for (int i = 0; i < P; i++) { bool found = false; for (int j = 0; j < p[i].ingredients.size(); j++) { if (p[i].ingredients[j].name == target_ingredient) { found = true; if (max_min < p[i].ingredients[j].min) { max_min = p[i].ingredients[j].min; } if (min_max > p[i].ingredients[j].max) { min_max = p[i].ingredients[j].max; } } } if (!found) { min_max = 0; } } bool first = true; for (int i = 0; i < P; i++) { bool found = false; for (int j = 0; j < p[i].ingredients.size(); j++) { if (p[i].ingredients[j].name == target_ingredient) { found = true; if ((word == "most" && p[i].ingredients[j].max >= max_min) || (word == "least" && p[i].ingredients[j].min <= min_max)) { cout << (first ? "" : " ") << p[i].name; first = false; } } } if (!found) { if (word == "least") { cout << (first ? "" : " ") << p[i].name; first = false; } } } cout << endl; } } return 0; }