28a Olimpíada Brasileira de Informática
Submeta sua solução

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.
Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

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
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação