|
Лимит времени 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
|
Для отправки решений необходимо выполнить вход.
|