| Автор: | А. Жуплев, А. Кленин | Ограничение времени: | 3 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 128 Мб | |
| Выходной файл: | output.txt |
Однажды крокодил Гена устроил парад шушанчиков. Для этого он взял несколько шушанчиков, окрашенных в разные цвета, и выстроил в ряд. Ряд задан строкой, в которой шушанчики разных цветов обозначены разными буквами.
Гена не любит повторений, поэтому, прохаживаясь перед строем, он находит и выгоняет группы из подряд стоящих шушанчиков, в которых цвет у первого шушанчика совпадает с последним, второго с предпоследним и т.д., так что вся группа выглядит одинаково при проходе слева направо и справа налево. Крокодил продолжает это делать до тех пор, пока либо шушанчики не закончатся, либо в оставшемся ряду ему не удастся найти ни одной такой группы.
Крокодил хочет узнать, какую строку минимально возможной длины он может получить путём таких операций и просит вас написать программу, отвечающую на этот вопрос.
Например, если ряд задан строкой abbbwwbba,
Гена может, например, поступить следующим образом:
abbbwwbba →
abwwbba →
abwbba →
abbba →
aba →
EMPTY
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|