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:

view plaincopy to clipboardprint?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <string.h>  
4.   
5. #define FALSE   0  
6. #define TRUE    1  
7.   
8. void main (void)  
9. {  
10.     int iCase, nCases;  
11.     int N, K;  
12.     int lOn, i, msk;  
13.   
14.     scanf ("%d\n", &nCases);  
15.     for (iCase = 1; iCase <= nCases; iCase++)  
16.     {  
17.         scanf ("%d %d\n", &N, &K);  
18.         lOn = FALSE;  
19.         msk = 1;  
20.         for (i = 0; i < N; i++)  
21.         {  
22.             if ((K & msk) == 0)  
23.             {  
24.                 lOn = FALSE;  
25.                 break;  
26.             }  
27.             lOn = TRUE;  
28.             msk <<= 1;  
29.         }  
30.         printf ("Case #%d: %s\n", iCase, lOn ? "ON" : "OFF");  
31.     }  
32. }  

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