Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Palindroms
- Английский учишь? Карточки с буквами… «zaraza»… это ты кому, Рома?
- Это программирование. Писал практическую, получился вирус, во всём кабинете
пришлось винду переустанавливать. Препод сказал, что за комп меня теперь вообще не пустит,
велел самому вместо процессора работать. Дал карточки с буквами, задал из них
собрать такую строку, чтобы как можно больше её подстрок были палиндромами.
- А, палиндромы… это строки, которые симметричные, слева направо и справа налево
читаются одинаково… слушай, давай от твоей «заразы» отцепим последнюю «a»
- получится «zaraz», это палиндром!
- Ты не понял, внутренние палиндромы тоже считаются. В «zaraz» будет 5 однобуквенных,
1 трёхбуквенный и 1 пятибуквенный, итого 7. А в «zaraza» - прибавятся
ещё одна «a» и «aza». Но ведь можно по-разному буквы перекладывать…
Итак, задача: дана строка из строчных букв латиницы длиной не более 100 символов. Требуется посчитать, какой максимальной палиндромистости можно добиться от этой строки, переставив в ней буквы.
Входные данные: одна строка из строчных букв латиницы длиной не более 100 символов.
Выходные данные:максимальное количество подстрок-палиндромов, которые можно получить
из строки, являющейся перестановкой символов исходной.
Для отправки решений необходимо выполнить вход.
|