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:

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