Ограничения: время – 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
Source: NEERC ICPC, Far Eastern subregion, 2009