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).

view plaincopy to clipboardprint?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <string.h>  
4.   
5. void main (void)  
6. {  
7.  int iCase, nCases;  
8.  int L, P, C;  
9.  int n, r;  
10.  long long prod;  
11.   
12.  scanf ("%d\n", &nCases);  
13.  for (iCase = 1; iCase <= nCases; iCase++)  
14.  {  
15.      scanf ("%d %d %d\n", &L, &P, &C);  
16.   
17.      prod = L;  
18.      n = 0;  
19.      while (prod < (long long) P)  
20.      {  
21.          prod *= C;  
22.          n++;  
23.      }  
24.      r = 0;  
25.      prod = 1;  
26.      while ((long long) n > prod)  
27.      {  
28.          prod = prod << 1;  
29.          r++;  
30.      }  
31.   
32.      printf ("Case #%d: %d\n", iCase, r);  
33.  }  
34. }  

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