Problem F
Problem Classification
When reading programming problems, one can often get some hints regarding the topic of the problem by skimming the problem statement for certain words. If, for example, the word “vertex” or “edge” appears, the problem is almost certainly a graph problem, while the words “words” or “letters” suggest that the problem is about strings.
Your task is to implement a simple program that attempts to classify a problem according to one of $N$ categories. Each category has an associated set of words, which, if they appear as words in a statement, suggest the problem belongs to this category. When classifying a statement, the program should suggest those categories which have the highest number of occurences of their associated words. Note that words that are part of other words do not count. For example, the word statement should not count as an occurance for the word ate.
In the above example, we suggested that the category graph may have the associated words vertex and edge and the category string could have the associated words words and letters. Then, if there were $3$ occurances each of the words vertex and edge, the number of matches for the category graph would be $6$. If the statement contained $14$ occurances of words and $4$ of letters, the number of matches for the category string would be $18$. Since there are more matches for the second category, the program should suggest it.
If there are multiple categories with the same number of matches, your program should suggest all of them.
Input
The first line of input contains the number of categories $1 \le N \le 10$.
The next $N$ lines each contain a description of a category. The description starts with the name of the category – a single word. Then, an integer $1 \le W \le 10$ follows – the number of words associated with this category. This is followed by those $W$ words, separated by spaces. No two words within a category are the same, and no two categories have the same name.
This is followed by a number of lines describing the statement of the problem. Each line contains a list of space-separated words.
Every word in the input will consist solely of at most $30$ lower-case letters a-z. The statement consists of between $1$ and $10\, 000$ words.
Output
For each suggested category, output the name of the category on a single line, in lexicographical order.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 datastructure 3 query range sum geometry 3 euclid range vertex graph 3 query vertex hamiltonian math 3 hamiltonian sum euclid consider the hamiltonian graph where each vertex corresponds to an linear equation we can solve these using the euclid algorithm now you will receive a query corresponding to a range of vertices your task is to compute the sum of the minimum solution of those vertices |
datastructure geometry graph math |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 graph 2 vertex edge string 2 words letters problem classification when reading programming problems one can often get some hints regarding the topic of the problem by skimming the problem statement for certain words if for example the word vertex or edge appears the problem is almost certainly a graph problem while the words words or letters suggest that the problem is about strings your task is to implement a simple program that attempts to classify a problem according to one of n categories each category has an associated set of words which if they appear as words in a statement suggest the problem belongs to this category when classifying a statement the program should suggest those categories which have the highest number of occurences of their associated words in the above example we suggested that the category graph may have the associated words vertex and edge and the category string could have the associated words words and letters then if there were occurances each of the words vertex and edge the number of matches for the category graph would be if the statement contained occurances of words and of letters the number of matches for the category string would be since there are more matches for the second category the program should suggest it if there are multiple categories with the same number of matches your program should suggest all of them input the first line of input contains the number of categories n the next n lines each contain a description of a category the description starts with the name of the category a single word then an integer w follows the number of words associated with this category this is followed by those w words separated by spaces this is followed by a number of lines describing the statement of the problem each line contains a list of spaceseparated words every word in the input will consist solely of lowercase letters a z output for each suggested category output the name of the category on a single line in lexicographical order |
string |
