Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

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

(Время: 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.TXTOUTPUT.TXT
1AAAAAAAAAABABABCCD9(A)3(AB)CCD
2NEERCYESYESYESNEERCYESYESYES2(NEERC3(YES))

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Олимпиадные задачи по программированию, 2006
 Тренировка 1
 Тренировка 2
 Тренировка 3
 Тренировка 4
 Тренировка 5
 Тренировка 6
 Тренировка 7
 Тренировка 8
 Тренировка 9
 Тренировка 10
 Тренировка 11
 Тренировка 12
 Тренировка 13
 Тренировка 14
 Тренировка 15
 A. Марковский цикл
 B. Д-44
 C. Упаковка символов
 D. Пирамиды
 E. Поле для крикета
 F. Электронная таблица

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru



дтп в стоячий автомобиль