HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50613 - Zapakovka

Guest
• Discussion of problem (1)

Section problems

• 50682 - Hotel Durres
• 50930 - Tom and Jerry
• 50526 - Gold Market
• 50488 - Connecting Wires
• 50681 - Center of a Series
• 50561 - Lucky tickets
• 50598 - Minimum Sum
• 50601 - Increasing sequence
• 50613 - Zapakovka
• 50680 - Triangle
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50544 - Stock market
• 50545 - Diet

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. Difficulty Gamma

Билл пытается компактно представить последовательность заглавных латинских букв от '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