ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Неотсортированные > задача:


Запаковка

Задачи раздела

• Ежевика
• Ездец
• Жадина
• Жадина
• Забавная игра
• Забор
• Забор
• Замок со штифтами
• Запаковка
• Зарплата продукцией
• Звёздно-полосатый
• Змейка
• Игра с разрезанием
• КВН
• Карта
• Кафе и такси
• Квадратное уравнение

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма

Билл пытается компактно представить последовательность заглавных латинских букв от 'A' до 'Z', с учетом повторяющихся последовательностей в ней. Например, возможный способ представить последовательность AAAAAAAAAABABABCCD - есть 10(A)2(BA)B2(C)D. Билл ввел формальное понятие упакованной последовательности так:
• Последовательность, содержащая один символ из диапазона 'A'..'Z' считается упакованной последовательностью. Ее распаковка возвращает тот же символ.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Причем, если результатом распаковки S является S', а Q - Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное целое число, большее 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.

Согласно этому определению легко распаковать любую запакованную последовательность. Но Билл более заинтересован в обратной операции. Он хочет запаковать данную последовательность так, чтобы результирующая запакованная последовательность содержала как можно меньше символов (включая цифры и скобки).

Ввод
Одна строка, состоящая не менее, чем из одного и не более чем из 100 символов в диапазоне 'A'..'Z'.
Вывод
Число - длину кратчайшего из вариантов запаковки исходной последовательности.

Ввод 1 Ввод 2
AAAAAAAAAABABABCCD
NEERCYESYESYESNEERCYESYESYES
Вывод 1 Вывод 2
12
14

Для отправки решений необходимо выполнить вход.

www.contester.ru