28a Olimpíada Brasileira de Informática
Código de Compressão
Em computação, compressão de arquivos é o processo de reduzir o tamanho de arquivos. Uma técnica simples mas eficiente de compressão para alguns tipos de arquivos é RLE, cujo o nome é derivado das letras iniciais do nome em inglês, que pode ser traduzido por codificação por comprimento de repetições. Em RLE, cada sequência de valores repetidos no arquivo é substituída pelo número de repetições seguido do valor a ser repetido. Por exemplo, a sequência `AAAAAA' seria substituída por `6 A'. Se o arquivo tem muitas sequências de valores repetidos, a técnica RLE é bem eficiente (por exemplo, considere um arquivo de imagem branco e preto em que grande parte dos valores é branco). Por outro lado, se o arquivo não possui muitas repetições, a técnica RLE pode aumentar o tamanho do arquivo, ao invés de diminuir. Nesta tarefa, dada uma cadeia de caracteres, você deve escrever um programa que produza a sequência de caracteres comprimida com a técnica RLE.Entrada
A primeira linha contém um inteiro N, o comprimento da cadeia de caracteres. A segunda linha contém a cadeia de caracteres, com N caracteres Ci.Saída
Seu programa deve produzir uma única linha, contendo a cadeia de caracteres codificada com a técnica RLE. A codificação consiste em uma sequência de pares, separados por espaços, em que cada par é um inteiro (indicando o número de repetições), seguido de um espaço, seguido do caractere a ser repetido.Restrições
- 1 ≤ N ≤ 1 000
- Ci é uma letra, maiúscula ou minúscula, não acentuada.
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:- Subtarefa 1 (21 pontos): Não há repetições na cadeia de entrada (veja exemplo 2).
- Subtarefa 2 (23 pontos): Ci= `a' ou Ci= `b' para todo i (veja exemplo 3).
- Subtarefa 3 (56 pontos): Nenhuma restrição adicional.
Exemplos
Entrada
8 TAAAAxxx |
Saída
1 T 4 A 3 x |
Entrada
4 XYZX |
Saída
1 X 1 Y 1 Z 1 X |
Entrada
21 aaaaaaaaaabbbbbbbbbbb |
Saída
10 a 11 b |