Google Code Jam 2011: QR_A - Bot Trust

O primeiro problema da rodada de qualificação não foi difícil, para resolvê-lo bastou fazer uma simulação seguindo a descrição do problema.

Resumo do Problema

Dois robôs estão em dois corredores. Cada corredor tem 100 botões, numerados de 1 a 100 e dispostos em ordem crescente. A cada segundo, cada um dos robôs pode fazer uma de três coisas: pressionar o botão a sua frente, ficar parado ou mover para um botão adjacente. Inicialmente os dois robôs estão em frente do botão número 1.

A entrada para o problema é uma lista de "missões" que devem ser executadas em ordem. Cada missão é descrita por um par (R, P) onde R indica qual dos dois robôs deve cumprir a missão e P é o botão a ser pressionado. A lista é conhecida previamente pelos dois robôs, permitindo que os dois robôs se movimentes simultaneamente para os seus respetivos alvos. Como as missões precisam ser executadas em ordem, não é permitido os dois robôs apertarem botões no mesmo segundo.

Deseja-se saber qual o menor tempo para cumprir a lista.

Minha Solução

Na minha solução eu simulei os dois robôs, segundo a segundo. Para cada robô eu mantive as seguintes informações:

• A posição atual (qual o número do botão na frente do robô)
• O número da missão que ele vai cumprir
• A posição especifica na missão (o destino)
• Um indicador que o robô já cumpriu todas as suas missões (esta informação é redundante com o número da missão)

Em C, estas informações são guardadas em um vetor contendo duas estruturas:

typedef struct
{
   int pos;
   int iMission;
   int dest;
   int finished;
} ROBOT;

ROBOT robot[2];

As missões são guardadas em um vetor onde cada posição indica o robô e o botão a ser pressionado. Duas variáveis inteiras guardam a quantidade de missões e o número da missão atual:

typedef struct
{
   int iRob;
   int iBut;
} MISSION;

MISSION mission [100];
int nMission;
int curMission;

O tempo atual é guardado em uma variável inteira, já que no pior caso um robô gasta 100 segundos para cumprir uma missão e podem existir até 100 missões:

int sec;

Definidas as estruturas de dados, vamos ao código. O primeiro passo é uma rotina para determinar qual a próxima missão de um robô. Para isto basta percorrer o vetor de missões a partir posição seguinte à última missão que ele completou:

void SetNextMission (int ir)
{
   int i;

   for (i = robot[ir].iMission+1; (i < nMission) && (mission[i].iRob != ir); i++)
       ;
   robot[ir].iMission = i;
   if (i < nMission)
       robot[ir].dest = mission[i].iBut;
   else
       robot[ir].finished = TRUE;
}

Uma segunda rotina implementa a lógica do cérebro positrônico do robô. Se ele já cumpriu todas as missões, fica parado. Se não está na frente do botão da missão que está executando, ele se move rumo a ele. Se está na frente do botão ele o aperta se a sua missão for a atual; caso contrário fica parado esperando o outro robô cumprir a(s) sua(s) missão(ões):

int MoveRobot (int ir)
{
   int im;

   if (robot[ir].finished)
       return FALSE;
   im = robot[ir].iMission;
   if (robot[ir].pos < mission[im].iBut)
       robot[ir].pos++;
   else if (robot[ir].pos > mission[im].iBut)
       robot[ir].pos--;
   else if (robot[ir].iMission == curMission)
   {
       SetNextMission (ir);
       return TRUE;
   }
   return FALSE;
}

A partir daí o programa principal praticamente se escreve sozinho. É preciso ler os dados, iniciar a simulação e executá-la até que os dois robôs tenham completado todas as suas missões:

void main (void)
{
   int iCase, nCases;
   int i;
   char cRob;
   int next;

   scanf ("%d\n", &nCases);
   for (iCase = 1; iCase <= nCases; iCase++)
   {
       scanf ("%d", &nMission);
       for (i = 0; i < nMission; i++)
       {
           scanf (" %c %d", &cRob, &mission[i].iBut);
           mission[i].iBut--;
           mission[i].iRob = (cRob == 'O') ? 0 : 1;
       }
       robot[0].pos = robot[1].pos = 0;
       robot[0].iMission = robot[1].iMission = -1;
       robot[0].finished = robot[1].finished = FALSE;
       SetNextMission (0);
       SetNextMission (1);
       curMission = 0;
       sec = 0;
       while (! (robot[0].finished && robot[1].finished))
       {
           sec++;
           next = MoveRobot(0);
           next = MoveRobot(1) || next;
           if (next)
               curMission++;
       }
       printf ("Case #%d: %d\n", iCase, sec);
   }
}