782 . Declaration of Content
Description
Most food you can buy at your local grocery store has a declaration of
content. The declaration of content lists the ingredients of the
product. It does not necessarily tell you the exact amount of every
ingredient, only the ordering of the ingredients, from most common to
least common. For some ingredients, an exact percentage might be
given, either required by law or because the producer wants you to know
how much of the fine expensive ingredients they have used.
Given a set of different products and their respective declarations of
content you should determine which contain the most or the least of
some given ingredients. For simplicity, we assume in this problem that
the percentage of each ingredient always is an integer.
Input Format
The input consists of several test cases. Each test case consists of
two parts.
The first part of a test case begins with an integer P, 1 ≤ P ≤
10, the number of different products in this test case, on a line of
its own. Then follows the description of the P products. Each product
description consists of a line giving the name of the product,
followed by a line containing an integer n, 1 ≤ n ≤ 100, giving
the number of ingredients in this product. Then follow n lines, the
i:th of which contains the name of the i:th most common ingredient of
the product. In case of ties, the ingredients will be listed in
arbitrary order. Optionally, every ingredient name can be followed by
space, an integer p, 0 ≤ p ≤ 100 and a percentage sign. If this
is present, it specifies the exact amount of this ingredient in the
product. Otherwise, because all percentages in this problem are
integers, the ingredient makes up at least one percent of the total
product.
The second part of a test case begins with an integer Q, 1 ≤ Q ≤
100, the number of queries. Then follow Q lines, each containing a
query. A query is of the form "least X", or "most
X", where X is the name of an ingredient. In the "most
X" case, the ingredient X is guaranteed to be present in at least
one of the products.
A name of a product or an ingredient is a string of alphabetic
characters (A-Z and a-z), digits (0-9) and underscore. Case is
significant. No name will be longer than 30 characters. You may assume
that each declaration of content is valid.
The last test case to be processed is followed by a
line consisting of the integer 0.
Output Format
The output consists of one line for every query in the input data.
For each query, output the name of the product containing the most
or the least of ingredient X, as indicated by the query. If there are several
possible such products, output all of them, in the same order as
the products were presented in the test case input data. The
product names should be separated by a single space.
Sample Input 1
3
Product_1
3
A
B
C
Product_2
3
C
B
A
Product_3
2
B
C 35%
4
most A
most B
most C
least D
0
Sample Output 1
Product_1
Product_3
Product_2 Product_3
Product_1 Product_2 Product_3
Hints
Problem Source
Migrated from old NTUJ.
nwerc2005
Subtasks
| No. | Testdata Range | Score |
|---|