Матч 432, Группированные слова (GroupedWord)

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

Слово называется группированным, если для каждой его буквы все ее появления в слове образуют в точности одну последовательность. То есть никакие две одинаковые буквы не разделяются другими. Например, слова “ccazzzzbb” и “code” являются группированными, а “aabbbccb” и “topcoder” нет.

Группированное слово разбили на несколько частей и расположили эти части в произвольном порядке в массиве parts. Необходимо восстановить и вернуть это группированное слово. Если существует более одного решения, вернуть “MANY”. Если восстановление невозможно, вернуть “IMPOSSIBLE”.

Класс: GroupedWord

Метод: string restore(vector<string> parts)

Ограничения: parts содержит от 1 до 50 строк, каждая из которых содержит от 1 до 20 символов ‘a’ – ‘z’.

Вход. Массив слов parts.

Выход. Восстановленное группированное слово. Вернуть “MANY”, если искомых слов может быть несколько, или “IMPOSSIBLE”, если восстановление невозможно.

Пример входа

parts

{"aaa", "a", "aa"}

{"ab", "bba"}

{"orr", "rd", "woo", "www"}

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

"aaaaaa"

"IMPOSSIBLE"

"wwwwooorrrd"

РЕШЕНИЕ

жадный алгоритм + обработка строк

Если строка является группированной, то и любая ее подстрока является группированной. Проверим, являются ли группированными слова массива parts при помощи функции test. Если хотя бы одно слово из parts[i] не является группированным, возвращаем “IMPOSSIBLE”.

Будем соединять любые два слова, которые можно соединить, до тех пор пока это возможно. Два слова p и s можно соединить, если слово p заканчивается на букву с, а слово s начинается на букву с. В таком случае вместо двух слов у нас появится слово p + s. При этом все слова, состоящие только из буквы с, необходимо поставить между p и s. Поэтому изначально присоединим все слова, состоящие из одинаковых букв, к словам, которые на них заканчиваются (функция join1), после чего будем стараться соединить все возможные пары слов при помощи функции join2.

После того как описанные объединения станут невозможными, объединим оставшиеся слова в произвольном порядке. Если полученное слово не является группированным, возвращаем “IMPOSSIBLE”. Иначе любые конкатенации оставшихся слов будут давать исходное возможное группированное слово. Если после описанных выше объединений останется одно слово, то возвращаем его. Иначе возвращаем “MANY”.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <numeric>

using namespace std;

int test(string s)

{

int i, j, k;

for(i = 0; i < s.size(); i++)

for(j = i + 1; j < s.size(); j++)

if (s[i] == s[j])

for(k = i; k <= j; k++)

if (s[i] != s[k]) return 0;

return 1;

}

int join1(vector<string> &v)

{

int i, j;

for(i = 0; i < v.size(); i++)

for(j = 0; j < v.size(); j++)

if (i != j)

{

char c = v[i][v[i].size() - 1];

if ((v[j][0] == c) && (v[j][v[j].size() - 1] == c))

{

v[i] += v[j];

v.erase(v.begin() + j);

return 1;

}

}

return 0;

}

int join2(vector<string> &v)

{

int i, j;

for(i = 0; i < v.size(); i++)

for(j = 0; j < v.size(); j++)

if (i != j)

{

if (v[j][0] == v[i][v[i].size() - 1])

{

v[i] += v[j];

v.erase(v.begin() + j);

return 1;

}

}

return 0;

}

class GroupedWord

{

public:

string restore(vector<string> parts)

{

int i;

for(i = 0; i < parts.size(); i++)

if (!test(parts[i])) return "IMPOSSIBLE";

while(join1(parts)); while(join2(parts));

for(i = 0; i < parts.size(); i++)

if (!test(parts[i])) return "IMPOSSIBLE";

string s = accumulate(parts.begin(),parts.end(),string());

if (!test(s)) return "IMPOSSIBLE";

if (parts.size() > 1) return "MANY";

return parts[0];

}

};