Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1306. Сокращение строки
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 10/01/2003 | Областная олимпиада школьников по информатике (командные соревнования) (4) |
| 19/11/2010 | Занятие 10 (G) |
| 30/06/2017 | Лето 2017 (1 курс, командное) - 2 (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Возьмем строку не более 255 букв, состоящую только из латинских букв a и b.
Можно выполнять сокращение строки по следующему правилу: подстрока a#a или b#b,
где символ # обозначает одну произвольную букву a или b,
может быть сокращена до подстроки #. Требуется получить строку минимальной длины после
нескольких таких сокращений. Например, из строки aaaaaab можно
получить строку aab.
Напишите программу, которая определяет минимально возможную длину
строки после выполнения сокращений.
Входной файл содержит начальную строку.
В выходной файл вывести одно целое число – минимальную длину конечной строки.
Пример ввода
aaaaaab
Пример вывода
3
