Декомпозиция строки
(Время: 3 сек. Память: 16 Мб Сложность: 65%)
Для строки T и целого числа n определим n-ю степень строки Tn как конкатенацию n копий строки T. Например, aab4 = aabaabaabaab.
Любая строка S может быть представлена в виде разложения S = S1d1S2d2 ... Skdk. Вообще говоря, такое разложение может быть не единственным. Весом разложения строки S в указанном виде назовем сумму |S1| + |S2| + . . . + |Sk|, где |Z| означает длину строки Z.
По заданной строке S найдите ее разложение с минимальным весом.
Входные данные
Входной файл INPUT.TXT содержит строку S. S состоит из заглавных английских букв и имеет длину не более 5000.
Выходные данные
Первая строка выходного файла OUTPUT.TXT должна содержать w – минимальный возможный вес разложения строки S. Пусть k – число элементов в таком разложении. Тогда следующие k строк должны содержать элементы разложения: строку Si и степень di, разделенные ровно одним пробелом.
Если существует несколько оптимальных решений, выведите любое из них.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | ABABAAABABA | 5
AB 2
A 3
BA 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
