Difference between revisions of "Problema da codificação da string"

Revision as of 03:09, 29 November 2008

Dificuldade Única

Um grupo de estudantes de Ciência da Computação de primeiro semestre decidiu criar um algoritmo para comprimir e códificar um textos. A técnica desenvolvida é bem simples.

Primeiro um texto de T caracteres (0<T<1000) contendo somente letras maiúsculas e números é convertido para uma cadeia contendo exclusivamente letras maiúsculas da seguinte forma:

• as letras diferentes de Z são copiadas na mesma ordem em que aparecerem.
• as letras Z são convertidas para a cadeia ZZ na mesma ordem em que aparecerem.
• caso um número seja encontrado ele é convertido em um par de letras sendo a primeira um Z e a segunda um A, caso o número seja 0, um B, caso o número seja 1, um C caso o número seja 2 e assim por diante até J caso o número seja 9.

A cadeia resultante desta primeira etapa é recodificada para eliminar repetições de caracteres. O procedimento consiste em uma variação da compressão RLE, assim:

• sendo A uma letra e K o número vezes sucessivas (sempre menor que 1000) que letra A é repetida, o resultado a ser exibido será KA, exceto se K for igual a 1 quando neste caso a saída será A.

Faça um programa capaz de codificar e de decodificar esta string.

A entrada e a saída serão as padrões (stdin,stdout).

Formato de entrada

• Uma linha contendo a letra C ou a letra D. Caso C então a próxima linha representará uma cadeia a ser codificada, caso D então a próxima linha deverá ser decodificada.
• Uma linha contendo a cadeia a ser processada.

Formato de saída

• Uma linha contendo o resultado do processamento ou, caso a cadeia de entrada não for válida, uma linha em branco.

Exemplos

Entrada 1

C
ABC

Saída 1

ABC

Entrada 2

C
AAAAAAAABC

Saída 2

8ABC

Entrada 3

C
ABCZ

Saída 3

ABC2Z

Entrada 4

C
ABCZ9Z

Saída 4

ABC3ZJ2Z

Entrada 5

D
2Z

Saída 5

Z

Entrada 6

C
1234567890

Saída 6

ZBZCZDZEZFZGZHZIZJZA

Entrada 7

D
Z

Saída

<Cadeia inválida, deve-se exibir uma linha em branco.>