Google Code Jam 2010: Theme Park

Theme Park (parque de diversões) foi o terceiro problema da Qualification Round do Code Jam 2010. O enunciado completo está no site oficial, mas o resumo é:

• "N" grupos de pessoas, cada um com g_i pessoas, passam o dia andando em uma montanha russa.
• Cada viagem da montanha russa suporta um máximo de "k" pessoas.
• A cada viagem os grupos vão entrando até que não caiba um grupo inteiro. Ao final da viagem os grupos voltam para o final da fila, mantendo a ordem.
• Ao longo do dia são feitas "R" viagens; cada pessoa gera uma receita de 1 euro por viagem.
• O problema é determinar a receita total.

Uma solução "força bruta", como implementar exatamente o que está escrito acima, é inadequada para o conjunto grande, onde podemos ter até 100.000.000 viagens e até 1.000 grupos.

Como a capacidade da montanha russa pode chegar a 1.000.000.000 de pessoas, o valor total pode chegar a 10^17. Isto estoura a capacidade de inteiros de 32bits mas cabe nos inteiros de 64 bits (o que eu não percebi inicialmente). O código adiante usa a sintaxe confusa do Visual C++ v6 para os inteiros de 64 bits.

A questão é como evitar ter que ficar somando um a um os grupos para cada viagem. Rabiscando um pouco, percebi que o grupo no início da fila define quantas pessoas vão na viagem e qual grupo ficará no início da fila. Isto pode ser calculado no início para os até 1.000 grupos, simplificando o cálculo para as até 100 milhões de viagens.

Para não correr riscos, tratei separado dois casos particulares:

• Todos os grupos podem ir em uma viagem.
• O primeiro grupo não cabe na montanha russa, impedindo todo mundo de viajar.

Segue o meu código:

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. #define MAX_N   1000  
9.   
10. typedef struct  
11. {  
12.     unsigned g;  
13.     __int64 sum;  
14.     unsigned next;  
15. } GROUP;  
16.   
17. GROUP grp [MAX_N];  
18.   
19. void main (void)  
20. {  
21.     int iCase, nCases;  
22.     int R, k, N;  
23.     int i, j;  
24.     __int64 total;  
25.   
26.     scanf ("%d\n", &nCases);  
27.     for (iCase = 1; iCase <= nCases; iCase++)  
28.     {  
29.         scanf ("%d %d %d\n", &R, &k, &N);  
30.         total = 0;  
31.         for (i = 0; i < N; i++)  
32.         {  
33.             scanf ("%d ", &grp[i].g);  
34.             total += grp[i].g;;  
35.         }  
36.   
37.         if (total < k)  
38.         {  
39.             // cabem todos  
40.             total = total * R;  
41.         }  
42.         else if (grp[0].g > k)  
43.         {  
44.             // primeiro grupo nao cabe  
45.             total = 0;  
46.         }  
47.         else  
48.         {  
49.             for (i = 0; i < N; i++)  
50.             {  
51.                 j = i;  
52.                 total = 0;  
53.                 while ((total + grp[j].g) <= k)  
54.                 {  
55.                     total += grp[j].g;  
56.                     if (++j >= N)  
57.                         j = 0;  
58.                 }  
59.                 grp[i].sum = total;  
60.                 grp[i].next = j;  
61.             }  
62.             total = 0;  
63.             j = 0;  
64.             for (i = 0; i < R; i++)  
65.             {  
66.                 total += grp[j].sum;  
67.                 j = grp[j].next;  
68.             }  
69.         }  
70.         printf ("Case #%d: %I64d\n", iCase, total);  
71.     }  
72. }  

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

#define FALSE   0
#define TRUE    1

#define MAX_N   1000

typedef struct
{
    unsigned g;
    __int64 sum;
    unsigned next;
} GROUP;

GROUP grp [MAX_N];

void main (void)
{
    int iCase, nCases;
    int R, k, N;
    int i, j;
    __int64 total;

    scanf ("%d\n", &nCases);
    for (iCase = 1; iCase <= nCases; iCase++)
    {
        scanf ("%d %d %d\n", &R, &k, &N);
        total = 0;
        for (i = 0; i < N; i++)
        {
            scanf ("%d ", &grp[i].g);
            total += grp[i].g;;
        }

        if (total < k)
        {
            // cabem todos
            total = total * R;
        }
        else if (grp[0].g > k)
        {
            // primeiro grupo nao cabe
            total = 0;
        }
        else
        {
            for (i = 0; i < N; i++)
            {
                j = i;
                total = 0;
                while ((total + grp[j].g) <= k)
                {
                    total += grp[j].g;
                    if (++j >= N)
                        j = 0;
                }
                grp[i].sum = total;
                grp[i].next = j;
            }
            total = 0;
            j = 0;
            for (i = 0; i < R; i++)
            {
                total += grp[j].sum;
                j = grp[j].next;
            }
        }
        printf ("Case #%d: %I64d\n", iCase, total);
    }
}