Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Печать | Помощь |
Задачи
1470. Improve RLE
Динамическое программирование и запоминающие функцииПоиск подстроки, префикс-функция, z-функция
Олимпиадные задачи на английском языке
| 24/06/2010 | Лето 2010 дорешивание (10I) |
| 14/07/2010 | Лето 2010 - 10 (I) |
| 15/04/2013 | Занятие 24 (F) |
| 22/04/2013 | Занятие 25 (F) |
| 05/05/2025 | ЦОП2: КМП (проводит BOGAT) (A) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
A computer programmer and mathematician Kumar Harikrishnan develops a new data compression system –
ACM (Advanced Compression Method) – which will incorporate all of his brilliant ideas.
The first component of ACM will be a modification of well-known RLE algorithm, called Improved RLE.
Since Kumar have much more difficult tasks to accomplish (such as to write Improved Hamming and Improved Lempel-Ziv),
he asks you to implement this simple, yet important part of a system.
An algorithm should replace repeating substrings of source string with a single instance of
substring concatenated with the number of repetitions. If some substring should not be repeated,
it is concatenated with number 1.
Your program must find the shortest possible compression of the given string.
Input file format
A single line of input file contains the string to be compressed.
It may contain spaces, but does not contain digits as Kumar has invented a complex digit-escaping
system to prevent uncompressing ambiguity.
Output file format
Output file must contain minimal length compression of the source string. There should be no
extra whitespace characters before or after the string.
Constraints
Length of the source string is from 1 to 1000 characters.
Sample Input 1
aaaaaaaaaa
Sample Output 1
a10
Sample Input 2
a c c c
Sample Output 2
a1 c3
Sample Input 3
abc
Sample Output 3
abc1
