Google Code jam 2010: Load Testing

Load Testing (teste de carga) foi o segundo problema da rodada 1C. Uma distração minha neste problema me impediu de obter a pontuação máxima na rodada.

O enunciado (que você encontra aqui) parece confuso na primeira leitura; felizmente os exemplos são mais claros. Tentando colocar de uma forma simples:

• Você precisa determinar qual o número mínimo de testes de carga a serem feitos em um site.
• Os testes são concluídos quando sabemos que o site suporta, dentro de um fator C, pelo menos P participantes ou uma quantidade X < P
  
• Suportar X participantes dentro de um fator C significa que você sabe que o site suporta uma carga a mas não uma carga a*C com a < P < a*C
  
• Inicialmente você sabe que o sistema suporta uma carga L mas não uma carga P.

Vamos considerar um dos exemplos do problema, no qual C=2, P=97 e L=24. Inicialmente sabemos que o site suporta até 47 participantes com fator 2 (pois 47 é o menor número menor que 2*24). Para termos certeza que o site suporta pelo menos 97 participantes com fator 2, precisamos testar com 49 (o menor número que multiplicado por 2 é maior que 97). Entretanto, se este teste for mal sucedido ainda não saberemos se o site suporta ou não 48 participantes. São precisos, portanto, dois testes.

Este exemplo sugere que os melhores pontos para teste são L*C, L*C*C, L*C*C*C, etc. É intuitivo que devemos primeiro tentar "no meio do caminho", usando um esquema parecido com a busca binária. Se L*C^(n-1) < P <= L*C^n, são precisos fazer, no pior caso, r = log2(n) (arredondado para cima se não for exato) casos.

Se ainda não ficou claro, veja a explicação oficial aqui.

A minha solução abaixo determina n e r "na marra". O meu erro na competição foi não reparar que L*C^n pode não caber em um inteiro de 32 bits. Na versão abaixo estou usando inteiro de 64 bits (o long long).

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

void main (void)
{
 int iCase, nCases;
 int L, P, C;
 int n, r;
 long long prod;

 scanf ("%d\n", &nCases);
 for (iCase = 1; iCase <= nCases; iCase++)
 {
     scanf ("%d %d %d\n", &L, &P, &C);

     prod = L;
     n = 0;
     while (prod < (long long) P)
     {
         prod *= C;
         n++;
     }
     r = 0;
     prod = 1;
     while ((long long) n > prod)
     {
         prod = prod << 1;
         r++;
     }

     printf ("Case #%d: %d\n", iCase, r);
 }
}