Google Code Jam 2008 - Text Messaging Outrage

Como comentei antes, participei das rodadas 1A e 1B. Resolvi dar uma olhada depois na rodada 1C e me deparei com uma surpresa: um problema fácil! Consegui resolvê-lo sem pressa em menos de meia hora, o que é bem melhor do que a minha experiência com os demais problemas.

O Problema

Retirando o lero-lero costumeiro, o problema é o seguinte: temos um teclado com K teclas, onde queremos colocar L letras. O teclado funciona como os teclados de celular, se tem duas letras na mesma tecla, é preciso apertar a tecla uma vez para a primeira letra e duas vezes para a segunda. Queremos reduzir o número de apertões para uma mensagem, sabendo quantas vezes ocorre cada letra na mensagem. A saída do programa é o número mínimo de apertões.

Tomando um exemplo simples: suponha que temos uma única tecla e duas letras (A e B). Se a mensagem a digitar tiver 3 Bs e 1 A, colocando [A B] na tecla são necessários 1 + 2*3 = 7 apertões, colocando [B A] reduzimos para 3 + 1*2 = 5.

A Solução

A solução me pareceu óbvia: ir colocando as letras nas teclas em ordem decrescente de ocorrência. Assim as letras mais comuns precisam de menos apertões. Ou seja:

• ler as ocorrências
• ordenar
• percorrer as letras ordenadas

Os limites para os small e large input são bem razoáveis, o único cuidado é que a quantidade de apertões pode estourar a capacidade de um int.

O Código

O código é bastante simples e direto. Usei a rotina qsort da biblioteca do C para ordenar, preferi não perder tempo escrevendo a minha própria rotina de ordenação.

#define MAX_LETTER 1000

int ocorre[MAX_LETTER];

int compare( const void *arg1, const void *arg2 )
{
 return *((int *)arg2) - *((int *)arg1);
}

void main (void)
{
 int iCase, nCases;
 int P, K, L;
 int j, nivel;
 __int64 apertos;

 scanf ("%d", &nCases);
 for (iCase = 1; iCase <= nCases; iCase++)
 {
   scanf ("%d %d %d", &P, &K, &L);
   for (j = 0; j < L; j++)
     scanf ("%d", &ocorre[j]);
   qsort (ocorre, L, sizeof (int), compare);
   nivel = 0;
   apertos = 0;
   for (j = 0; j < L; j++)
   {
     if ((j  % K) == 0)
       nivel++;
     apertos += ocorre[j] * nivel;
   }
   printf ("Case #%d: %I64d\n", iCase, apertos);
 }
}

Reparar que P (número máximo de letras por tecla) não é utilizado. O teste (j % K) é um truquezinho para detectar quando acabamos de percorrer todas as teclas e vamos recomeçar da primeira, um nível abaixo.

Vamos ver se na rodada de hoje vai ter algum problema simples assim.

OBS: Segundo o blogger, este é o post 200 do blog!