e-olymp
Задачі

Пакування символів

Пакування символів

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

Вихідні дані

У єдиному рядку виводиться упакована послідовність найменшої довжини, яка розпаковується у задану послідовність. Якщо таких послідовностей декілька, можна вивести довільну.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
Sample 1
AAAAAAAAAABABABCCD

Sample 2
NEERCYESYESYESNEERCYESYESYES
Вихідні дані
Sample 1
9(A)3(AB)CCD

Sample 2
2(NEERC3(YES))