|
Упаковка символов
(Время: 1 сек. Память: 16 Мб Сложность: 52%)
Билл пытается компактно представить последовательности прописных символов от 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 раз.
Следуя этим правилам, легко распаковать любую заданную упакованную последовательность. Однако Биллу более интересен обратный переход. Он хочет упаковать заданную последовательность так, чтобы результирующая сжатая последовательность содержала наименьшее возможное число символов.
Входные данные
Входной файл INPUT.TXT содержит последовательность символов от A до Z. Длина последовательности от 1 до 100.
Выходные данные
В выходной файл OUTPUT.TXT выведите упакованную последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, выведите любую.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | AAAAAAAAAABABABCCD | 9(A)3(AB)CCD |
2 | NEERCYESYESYESNEERCYESYESYES | 2(NEERC3(YES)) |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |