| Algo Cup 2025 by csspace.io (Финал) |
|---|
| Закончено |
Вам дан набор строк $$$s_1, s_2, \dots, s_n$$$, состоящих из строчных букв латинского алфавита. Гарантируется, что $$$n$$$ — чётное число.
Скажем, что строка $$$t$$$ идеальная, если ровно $$$\frac{n}{2}$$$ строк из набора содержат $$$t$$$ в качестве подстроки. Например, для набора abc, acb, cab и cba строки ab и cb являются идеальными, а строки a, ca, ooo — нет.
Ваша задача — найти самую длинную идеальную строку для заданного набора или сообщить, что такой не существует.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 1\,000$$$). Число $$$n$$$ — чётное.
Далее следуют $$$n$$$ строк, $$$i$$$-я из них содержит строку $$$s_i$$$, состоящую из строчных букв латинского алфавита. Сумма длин строк в наборе не превосходит $$$5\,000$$$.
В единственной строке выведите самую длинную идеальную строку. Если такой строки не существует, выведите "No solution" (без кавычек). Если возможных ответов несколько, выведите любой из них.
4abcacbcabcba
ab
2cccdd
ccc
4acddbaedaaaad
No solution
2xxxx
No solution
| Название |
|---|


