e-olymp
Məsələlər

Упаковка символов

Упаковка символов

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

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

Входные данные

В первой строке находится последовательность символов от A до Z. Длина исходной последовательности от 1 до 100.

Выходные данные

В единственной строке выводится упакованная последовательность наименьшей длины, которая распаковывается в заданную последовательность. Если таких последовательностей несколько, можно выводить любую.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
AAAAAAAAAABABABCCD
Çıxış verilənləri #1
9(A)3(AB)CCD