print1470. Improve RLE

printImprove RLE

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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.
Length of the source string is from 1 to 1000 characters.

Sample Input 1


Sample Output 1


Sample Input 2

a c c c

Sample Output 2

a1 c3

Sample Input 3


Sample Output 3

Source: NEERC ICPC, Far Eastern subregion, 2009