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");
    }
}