MadBrat

MadBrat

пикабушник
поставил 22851 плюс и 12257 минусов
проголосовал за 0 редактирований
4273 рейтинг 2 подписчика 1539 комментариев 18 постов 1 в горячем
1 награда
5 лет на Пикабу
-19

Подскажите в интернете ответ решение задачи

Задача 14С. Упаковка символов


Билл пытается компактно представить последовательности прописных символов от А до Z с помощью упаковки повторяющихся подпоследовательностей внутри них. Например, один из способов представить последовательность AAAAAAAAAABABABCCD — это 10(A)2(BA)B2(C)D. Он формально определяет сжатые последовательности символов и правила перевода их в несжатый вид следующим образом:

• Последовательность, содержащая один символ от А до Z, является упакованной. Распаковка этой последовательности дает ту же последовательность из одного символа.

• Если S и Q — упакованные последовательности, то SQ — также упакованная последовательность. Если S распаковывается в S', a Q распаковывается в Q', то SQ распаковывается в S' Q'.

• Если S — упакованная последовательность, то X (S) — также упакованная последовательность, где X — десятичное представление целого числа, большего 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.

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

Ввод из файла fotding.in. В первой строке находится последовательность символов от А до Z.

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

Примеры

Ввод

AAAAAAAAAABABABCCD

Вывод

9(A)3(AB)CCD

Ввод

NEERCYESYESYESNEERCYESYESYES

Вывод

2(NEERC3(YES))


http://www.itmathrepetitor.ru/menshikov-zadachi-iz-trenirovk...

Отличная работа, все прочитано!