Матч 336, Названия сервисов (ServiceNames)

Дивизион 2, Уровень 2

Набор сервисов, с каждым из которых связаны некоторые действия, описывается массивом строк. Первым словом в каждой строке стоит название сервиса, за которым следуют связанные с ним действия. Необходимо составить список всех действий, для каждого из которых найти все сервисы, в которых они встречаются.

Класс: ServiceNames

Метод: vector<string> makeList(vector<string> services)

Ограничения: services содержит от 1 до 50 строк длины не более 50 символов ‘A’-‘Z’,‘a’-‘z’, названия сервисов в каждой строке уникальны.

Вход. Массив строк services, описывающий сервисы.

Выход. Массив строк, содержащий список действий в лексикографическом порядке, за которыми следует стрелка в виде “==>” и названия сервисов, в которых встречаются эти действия. Последовательность сервисов для каждого действия должна выводиться в лексикографическом порядке. Сервисы разделять запятыми, после каждой запятой следует ставить один пробел.

Пример входа

Services

{"BLAST Genome Annotation Sensitivity","PING","X Annotation"}

{"PING"}

{"BLAST Genome annotation Sensitivity","PING","X Annotation",

"Apple X ample"}

Пример выхода

{"Annotation ==> BLAST, X", "Genome ==> BLAST", "Sensitivity ==> BLAST" }

{}

{"Annotation ==> X","Genome ==> BLAST","Sensitivity ==> BLAST","X ==> Apple",

"ample ==> Apple","annotation ==> BLAST" }

РЕШЕНИЕ

обработка строк + структуры данных

Каждому действию поставим в соответствие набор сервисов, в которых оно встречается при помощи отображения map. Набор сервисов для каждого действия будем хранить во множестве set.

Читаем входные данные, строим отображение m, связывающее действия с набором сервисов. Затем проходим по каждому действию и строим выходные строки, содержащие его название, стрелку и список сервисов, в которых оно встречается.

ПРОГРАММА

#include <cstdio>

#include <set>

#include <map>

#include <vector>

#include <string>

#include <algorithm>

#include <sstream>

using namespace std;

class ServiceNames

{

public:

map<string,set<string> > m;

map<string,set<string> >::iterator iter;

set<string>::iterator s_iter;

set<string> temp;

string a, b;

vector<string> res;

vector<string> makeList(vector<string> services)

{

for(int i = 0; i <services.size(); i++)

{

stringstream s(services[i]);

s >> a;

while (s >> b) m[b].insert(a);

}

for(iter = m.begin(); iter != m.end(); iter++)

{

a = (*iter).first + " ==> ";

temp = (*iter).second;

for(s_iter = temp.begin(); s_iter != temp.end(); s_iter++)

a = a + (*s_iter) + ", ";

a = a.substr(0,a.size() - 2);

res.push_back(a);

}

return res;

}

};