10686 – SQF Problems UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1627

Data structures, STL map, STL set.

How I did it

• I read the number cases.
• For each case I read the number of categories.
• I read the category name, the words and the needed words. I save this in a map “key= category name, value= number of words and the needed words.
• I read the words for the category and I save this in another map “key=category name” value= the words. (Here carefull saving the same word two or three time, for that im using a set).
• I read the other lines and save the words into a set.
• I traverse the words  of the last line and check every category. Compare the quantity with the first map.
• Print the answer.

Hints

•  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.
• The end of a problem description is indicated by a blank line.
• Just keep the category problem as a key in every map.

Input

3
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.

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 node, edge directed.
This is a boring geometrical problem. In this problem
you should calculate the convex area of a regular polygon.

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 boringa geometrical problem. In this problem
you should calculate the convexaaa area of a regular polygodsn.

Output

Geometrical
Graph,Geometrical
SQF Problem

Code

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <cctype>
#include <algorithm>

using namespace std;

map<string, pair<int,int> > catMap;
map<string, set<string> >  myMap;
vector<string> vec;
vector<string> ansVec;
set<string> mySet;

void init()
{
    catMap.clear();
    myMap.clear();
    vec.clear();
    ansVec.clear();
    mySet.clear();
}

void getWords(string str)
{
    string word = "";
    for(int x=0; x<str.size(); x++)
    {
        if(isalpha(str[x]))
           word += str[x];
        else if(word.size() != 0)
        {
            mySet.insert(word);
            word = "";
        }
    }
    if(word.size() != 0)
       mySet.insert(word);
}

void getAns()
{
    string tmp;
    int cont;
    for(int x=0; x<vec.size(); x++)
    {
        tmp = vec[x];
        set<string> cSet = myMap[tmp];
        cont = 0;

        for(set<string>::iterator it = mySet.begin(); it!=mySet.end(); it++)
        {
            if(cSet.find(*it) != cSet.end())
               cont++;
        }

        if(cont >= catMap[tmp].second)
           ansVec.push_back(tmp);
    }
}

int main()
{
    int casos, categorias, words, needed;
    string catName, str;

    scanf("%d", &casos);

    while(casos--)
    {
        init();
        scanf("%d", &categorias);
        for(int i=0; i<categorias; i++)
        {
            cin>>catName;
            vec.push_back(catName);
            scanf("%d %d", &words, &needed);
            pair<int,int> p = make_pair(words, needed);
            catMap[catName] = p;

            for(int j=0; j<words; j++)
            {
                cin>>str;
                myMap[catName].insert(str);
            }
        }
        getline(cin, str);//trash
        while(getline(cin, str))
        {
            if(str.size() == 0)
               break;
            getWords(str);
        }
        getAns();

        if(ansVec.size() == 0)
           printf("SQF Problem.\n");
        else
        {
            for(int g=0; g<ansVec.size() - 1; g++)
            {
                cout<<ansVec[g]<<',';
            }
            cout<<ansVec[ansVec.size() - 1]<<'\n';
        }
    }
return 0;
}