quarta-feira, maio 12, 2010

Google Code Jam 2010: Snapper Chain

Snapper Chain ("cadeia de estaladores") foi o primeiro problema da Qualification Round do Code Jam 2010. O enunciado completo está no site oficial, mas o resumo é:
  • O "estalador" (snapper) é um interruptor que, quando alimentado, muda de estado entre ligado e desligado quando alguém estala os dedos.
  • "N" estaladores são ligados em série. O primeiro é ligado na tomada e o último a uma lâmpada.
  • O problema consiste em determinar se a lâmpada estará acesa ou apagada após "K" estalos.
A solução de simular diretamente o funcionamento é inadequada para o conjunto grande, que pode ter até 30 estaladores tratando até 100.000.000 estalos.

O meu primeiro passo para a solução foi observar que na verdade cada estalador tem dois estados: alimentado ou não e ligado ou desligado. O estado ligado ou desligado só muda com um estalo se o estalador estiver alimentado, o que corresponde a todos os anteriores estarem ligados.

Simulando um pouco na mão, dá para perceber que a cadeia de estaladores corresponde a um contador binário. Após "K" estalos, o estado ligado/desligado da cadeia corresponde a "K" em binário (mais precisamente, K módulo 2^N). Todos os estaladores ligados corresponde a todos os bits em "1".

Meu algorítimo consiste, portanto, em testar se "K" tem os "N" bits menos significativos em "1". O tempo de execução depende apenas de "N" (cujo valor máximo é 30).

O código é o seguinte:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FALSE 0
#define TRUE 1

void main (void)
{
int iCase, nCases;
int N, K;
int lOn, i, msk;

scanf ("%d\n", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
scanf ("%d %d\n", &N, &K);
lOn = FALSE;
msk = 1;
for (i = 0; i < N; i++)
{
if ((K & msk) == 0)
{
lOn = FALSE;
break;
}
lOn = TRUE;
msk <<= 1;
}
printf ("Case #%d: %s\n", iCase, lOn ? "ON" : "OFF");
}
}

Nenhum comentário: