Слово называется сгруппированным, если для каждой его буквы
все ее появления в слове образуют в точности одну последовательность. То есть
никакие две одинаковые буквы не разделяются другими. Например, слова
“ccazzzzbb” и “code” являются сгруппированными, а “aabbbccb” и “topcoder” нет.
Сгруппированное слово разбили на несколько частей и
расположили эти части в произвольном порядке. Необходимо восстановить это
сгруппированное слово.
Вход. Состоит из нескольких тестов. Первая строка каждого теста
содержит количество частей слова n (1
≤ n ≤ 50). Вторая строка
содержит n частей слова в
произвольном порядке. Длина каждой части состоит из не более 20 символов 'a' -
'z'.
Выход. Для каждого теста вывести в отдельной строке
сгруппированное слово. Если существует несколько решений, то вывести
"MANY". Если слово не может быть создано из заданных частей, то
вывести "IMPOSSIBLE".
|
Пример входа |
Пример выхода |
|
3 aaa a
aa 2 ab
bba 4 orr
rd woo www 1 abcb |
aaaaaa IMPOSSIBLE wwwwooorrrd IMPOSSIBLE |
РЕШЕНИЕ
жадный алгоритм
Анализ
алгоритма
Если строка является сгруппированной, то и любая ее подстрока
является сгруппированной. Проверим, являются ли сгруппированными входные слова
при помощи функции test. Если хотя бы одно слово не является сгруппированным,
возвращаем “IMPOSSIBLE”.
Будем соединять любые два слова, которые можно соединить, до
тех пор пока это возможно. Два слова p
и s можно соединить, если слово p заканчивается на букву с, а слово s начинается на букву с.
В таком случае вместо двух слов у нас появится слово p + s. При этом все
слова, состоящие только из буквы с,
необходимо поставить между p и s. Поэтому изначально присоединим все
слова, состоящие из одинаковых букв, к словам, которые на них заканчиваются
(функция join1), после чего будем стараться соединить все возможные пары слов
при помощи функции join2.
После того как описанные объединения станут невозможными,
объединим оставшиеся слова в произвольном порядке. Если полученное слово не
является группированным, возвращаем “IMPOSSIBLE”. Иначе любые конкатенации
оставшихся слов будут давать исходное возможное группированное слово. Если
после описанных выше объединений останется одно слово, то возвращаем его. Иначе
возвращаем “MANY”.
Реализация
алгоритма
Входные слова для каждого теста сохраняем в массиве parts.
vector<string> parts;
Функция test проверяет, является
ли слово s группированным.
int test(string s)
{
int i, j, k;
Перебираем пары букв si и sj.
for(i = 0; i < s.size(); i++)
for(j = i + 1; j < s.size(); j++)
Если si и sj – одинаковые буквы, то все буквы между
индексами i и j должны быть одинаковыми.
if (s[i] == s[j])
for(k = i; k <= j; k++)
Если si ≠ sk (i ≤ k ≤ j), то
слово s не является сгруппированным.
if
(s[i] != s[k]) return 0;
return 1;
}
Функция join1 старается присоединить
слово, состоящее из одинаковых букв, к слову, которое на эту букву заканчивается.
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];
Если первая и последняя буквы j-го слова одинаковы, то все j-ое слово состоит из одинаковых букв.
Функция join1 уже будет вызываться на наборе сгруппированных слов.
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;
}
Функция join2 старается найти и соединить возможную пару
слов.
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)
{
Если первая буква j-го слова совпадает с последней буквой i-го слова, то припишем к i-му слову j-ое. После чего удаляем j-ое
слово из набора слов.
if (v[j][0] == v[i][v[i].size() - 1])
{
v[i] += v[j];
v.erase(v.begin() + j);
return 1;
}
}
return 0;
}
Функция restore возвращает
сгруппированное слово. Если сгруппировать входные слова невозможно, то
возвращается IMPOSSIBLE. Если существует несколько решений, то функция
возвращает MANY.
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];
}
Основная часть программы.
while(scanf("%d\n",&n)
== 1)
{
parts.clear();
for(i = 0; i < n; i++)
{
Заносим части слова в вектор parts.
scanf("%s",s);
parts.push_back(s);
}
res = restore(parts);
printf("%s\n",res.c_str());
}