[UVA][模擬] 10686 - SQF Problems
Problem F - SQF Problems
Time Limit: 1 second
Memory Limit: 1 Mb
Juciano, Sebastião e Sérgio formed a very good ACM team. They used to do a lot of problems but they were not organized and they have never classified the problems when they solved them.
As the ACM South America Regional was approaching, they decided to classify all their problems. Of course, there were hundreds of problems and they decided to apply a sistematic approach to speed up the process.
In their approach a problem would be classified based in key words. As example, a graph problem would be identified by words as: node, edge, distance etc. On the other hand, typical words in geometrical problems are: point, convex, polygon etc.
But a lot of problems could not be classified, because they did not fit in any category. Coincidently, Sérgio had solved all unclassified problems, because he spent his time trying to do ACM problems but almost all were very easy. So Juciano and Sebastião decided to classify these unclassified problems as SQF, that is mean: made by Sérgio (Sérgio que fez, in Portuguese).
Your task is help them to classify their problems. A problem can be fit in more than one category, if the problem did not fit in any category, it is a SQF problem.
Input
The input set consists of a positive number N ≤ 30, that gives the number of test cases. Each test case starts with a number C ≤ 20, the number of categories. After, each category is described by a string S, the name of the category, and two ingegers W ≤ 10, the number of key words in this category, and P, how many different words should appear in the description problem so the problem fits in this category. Follow W lines, each one with a key word of this category. All names are less than 31 characters, all in the range a..z and A..Z.
Finally, there will be the problem description, with at most 1200 lines, each line has fewer than 101 characters and there are no words divided between two lines. The words are case sensitive and two words are equals only if they match exactly. The end of a problem description is indicated by a blank line.
Output
For each input set, you shoud output a line indicating the problem's category. If the problem fits in more than one category, you shoud print them all, in the order they appear in the input, separated only by commas. If the problem does not fit in any category you should print "SQF Problem.", without the quotes.
Sample input
1
2
Graph 4 3 node
edge
directed
distance Geometrical 4 2 point
convex
polygon
boring This is neither a SQF problem nor a graph problem. This is a boring geometrical problem. In this problem you should calculate the convex area of a regular polygon.
Sample output
Geometrical
Problem setters: Sérgio Queiroz de Medeiros and Sebastião Alves
#include <stdio.h>
#include <map>
#include <iostream>
#include <ctype.h>
using namespace std;
int main() {
int t, n, i, j;
string pro[30], word, line;
int W[30], P[30];
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
map<string, int> R[30];
for(i = 0; i < n; i++) {
cin >> pro[i] >> W[i] >> P[i];
for(j = 0; j < W[i]; j++) {
cin >> word;
R[i][word] = 0;
}
}
cin.ignore(256, '\n');
while(getline(cin, line)) {
int len = line.length();
if(len == 0) break;
for(i = 0; i < len; i++) {
if(isalpha(line[i])) {
char buf[100], idx = 0;
while(i < len && isalpha(line[i]))
buf[idx++] = line[i++];
buf[idx] = '\0';
for(j = 0; j < n; j++) {
if(R[j].find(buf) != R[j].end()) {
R[j][buf] = 1;
}
}
}
}
}
int first = 0;
for(i = 0; i < n; i++) {
int cnt = 0;
for(map<string, int>::iterator it = R[i].begin();
it != R[i].end(); it++) {
cnt += it->second;
}
if(cnt >= P[i]) {
first++;
if(first != 1) printf(",");
cout << pro[i];
}
}
if(!first)
cout << "SQF Problem.";
cout << endl;
}
return 0;
}