Feira de Bactérias

 

           Tarefa
           Bruno pediu sua ajuda para decidir qual é o melhor tipode bactéria paraa compra. Lembre que para  Bruno o melhor tipo de bactéria é aquele cuja colônia,ao final do períodode crescimento,terá a maior quantidade de bactérias. Você deve supor que não haverá duas colônias coma mesma população final de bactérias.

Entrada
Na primeira linha, temos um número N representando o número de Bactérias seguindo por N linhas com dois números inteiros D e C onde D é quantidade de bactérias que cada bactéria deste tipo gera ao se dividir numa noite, e C é a quantidadede dias que a população de bactérias crescerá.
Saída
Um número inteiro entre 0 e N - 1 representando o tipo da bactéria que Bruno deverá comprar.

Idéias

Temos que encontrar a maior potenciação (a^b) entre todos os valores de a e b dados.

Mas como comparar duas potenciações (a^b, c^d) se não podemos calculá-la por que podemos ter um overflow. Temos que utilizar um método para conseguir reduzir esses valores.

Vamos utilizar a função logarítmica que consegue transformar multiplicações em adições. Os logaritmos eram bastante úteis antes do advento das calculadoras eletrônicas. Mesmo nas calculadoras atuais a função logarítmica ainda é bastante útil por causa da sua continuidade. Quando você faz 10^π, a calculadora usa a seguinte fórmula:

e ^{π ln(10)}

Mas voltando ao problema original como comparar duas potenciações (a^b, c^d).

a^b   > c^d  →    ln(a^b) > ln(c^d) →    b *ln(a) > d *ln(c)

#include 
#include 

Solução oficial dada pela organização da Olimpíada Brasileira de Informática

Mas vamos imaginar que não soubéssemos que existe a função log no arquivo de cabeçalho math.h. E agora,José?

Sabemos que a soma da série harmônica 1,1/2,1/3,… diverge, ou seja,

para valores grandes de n, a soma dos n primeiros termos da série podem ser bem aproximados 

 

#include 
#include 

Saída
100
100 4.605170 5.187378
1000
1000 6.907755 7.485471
10000
10000 9.210340 9.787606
100000
100000 11.512925 12.090146
1000000
1000000 13.815511 14.392727


Note que à medida que n vai crescendo a aproximação torna-se melhor. Mas vamos supor que você ainda não está ainda satisfeito e quer uma aproximação ainda melhor. Estamos podemos apelar para as aulas de cálculo I e para a seguinte fórmula.

 

Então precisamos desenvolver um método para resolver esta integral por uma aproximação da área da área abaixo da curva.

Podemos utilizar a regra do trapézio simples para tentar aproximar a área abaixo da curva.

A = [f(x₀) + f(x₁) ](b-a) /2

Podemos decompor este intervalo em sub-intervalos cada vez mais pequenos , e nesses sub-intervalos podemos aplicar a regra do trapézio da maneira mais conveniente.

Podemos decompor este intervalo em sub-intervalos cada vez mais pequenos , e nesses sub-intervalos podemos aplicar a regra do trapézio da maneira mais conveniente.

Podemos aproximar a região da curva decompondo a curva fixando um número de intervalos. Vamos considerar o número de intervalos igual ao número n.

#include <stdio.h>
#include <math.h>
#define eps 1.0e-6
double ln(int n,double intervalos){
 double fa =1, fb , area = 0.0;
 double largura = (n - 1) / intervalos;  
 double x;
 x = 1.0;
   while ( x <= 1.0*n - eps ){
  x = x + largura;
  fb = 1.0/x;
  area = area + ((fa + fb)*(largura))/2.0;
  fa = fb;
 }
 return area;
}
int main(){
 int n;
 while( scanf("%d",&n)  && n!=0 ){
  printf("%d %lf %lf\n",n,log(n) , ln(n,n*1.0) );
 }
}

Saída
100
100 4.605170 4.680934
1000
1000 6.907755 6.984826
10000
10000 9.210340 9.287542


Será que podemos fazer ainda melhor? Vou utilizar agora um método que não decompõe todos os intervalos do mesmo tamanho. Este método divide um intervalo da melhor maneira possível considerando uma tolerância eps. A escolha de dividir ou não um intervalo será baseado no valor da tolerância e na característica da curva. Este método é chamado quadratura adaptativa. 

Primeiramente, vamos calcular o ponto médio m entre a e b. Então vamos aproximar a área de três regiões sobre a curva definida pela função f(): a para m, m para b e a para b. Se a soma das duas regiões menores está dentro da tolerância da maior área, então a aproximação é considerada boa o bastante. Se não, o problema inicial – região de a para b – é dividido em duas sub-regiões – de a para m e m para b – e o  processo repete-se.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define eps 1.0e-6
double f(double x){
 return 1.0/x;
}
double area(double a, double b){
 return (f(a) + f(b))*(b-a)/2.0;
}
double quad(double esq, double dir ){ 
 double m = (esq + dir)/2.0;
 double area_esq = area(esq,m);
 double area_dir = area(m,dir);
 double area_total = area(esq,dir);
 if(fabs( (area_esq + area_dir) - area_total) > eps ){
  area_esq = quad(esq,m);
  area_dir = quad(m,dir); 
 }
 return (area_esq+area_dir); 
}
int main(){
 int n;
 while( scanf("%d",&n)  && n!=0 ){
  printf("%d %lf %lf\n",n,log(n) , quad(1,n) );
 }
}

Saída:

10
10 2.302585 2.302606
100
100 4.605170 4.605212
1000
1000 6.907755 6.907817
10000
10000 9.210340 9.210424
100000
100000 11.512925 11.513029


“Qualquer tecnologia suficientemente avançada é indistinguível da magia”

Arthur C. Clarke