Заклинание Ауэрса
(Время: 1 сек. Память: 16 Мб Сложность: 51%)
Заклинание Ауэрса представляет собой набор звуков, записываемых малыми буквами английского алфавита без пробелов. Сам по себе этот набор не обладает ни секретностью, ни магической силой и приведен во всех учебниках по белой магии в соответствующем разделе. Там же указан способ его применения:
а) разбить набор букв на палиндромы, то есть непустые слова, которые читаются одинаково как справа налево, так и слева направо;
б) произносить их по порядку, после каждого, взмахивая умклайдетом (в крайнем случае, щелкая пальцами);
в) магическая сила заклинания обратно пропорциональна числу палиндромов, на которые разбит набор букв.
Даже домовые знают, что это заклинание можно разбить на отдельные буквы и очень забавно наблюдать, как они, щелкая пальцами и выкрикивая отдельные звуки заклинания, выводят клопов. Однако истинную мощь заклинание обретает только тогда, когда оно разбито на наименьшее возможное число палиндромов. Знание этого разбиения доступно только самым великим магам, например Кристобалю Хозевичу Хунте.
Желая поднять свою квалификацию мага, Александр Привалов решил использовать современные средства для нахождения кратчайшего разбиения заклинания Ауэрса на палиндромы. Уже неделю он бьется над составлением переборной программы для своего Алдана, но пока все без толку. У него уже начала расти шерсть на ушах, помогите ему.
Входные данные
В единственной строке файла INPUT.TXT содержится непустой исходный набор, состоящий из маленьких букв английского алфавита без пробелов (количество символов в наборе не больше 70).
Выходные данные
В первой строке выходного файла OUTPUT.TXT необходимо указать наименьшее число k палиндромов, на которые разбивается набор. Эти k палиндромов нужно привести в следующих k строках в том порядке, в котором они входят в исходный набор и должны произноситься при использовании заклинания. Если имеется несколько минимальных разбиений, достаточно вывести любое из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | baobab | 4
b
a
o
bab |
| 2 | aaaaa | 1
aaaaa |
| 3 | rarabar | 3
rar
aba
r |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
