Cookie Clicker Alpha (Code Jam 2014)

Link al problemaProblem B. Cookie Clicker Alpha

Dificultad: Fácil

Problema:
El problema es una simulación basada en un juego, para este caso particular se tiene que el jugador comienza con $0$ galletas y gana $2$ por segundo, una vez que después de cierto tiempo junta $C$ ($1 ≤ C ≤ 10^4$) galletas, puede comprar una fábrica que le otorgará que aumentará en $F$ ($1 ≤ F ≤ 100$) la cantidad de galletas producidas por segundo.

El juego termina una vez que el jugador tiene $X$ ($1 ≤ X ≤ 10^5$) galletas que no ha gastado en fábricas. Ahora es nuestro turno de responder cuál es el menor tiempo en el que podemos terminar el juego.

Solución:
La solución podemos obtenerla analizando el caso de prueba, que tiene como valores de entrada: $C=500.0$, $F=4.0$ y $X=2000.0$. Ejecutando la simulación para que realice la simulación de comprar (en este caso) hasta 10 fábricas aumentando con ello la cantidad de galletas producidas por segundo y obteniendo menor de los tiempos en el que se completará la tarea de juntar $X$ cantidad por cada nueva fábrica comprada. En la siguiente tabla se observan los resultados de la simulación y en la gráfica se observa mejor lo que sucede:
De la gráfica se observa que solo existe mínimo absoluto, ya que a partir de cierta cantidad de fábricas comprada a pesar de que es más rápido obtener las cantidad, el tiempo gastado en comprar fábricas hace que ya no sea una opción viable.

Por tanto es solo necesario verificar el punto en el que nuestro tiempo para llegar al objetivo comience a crecer.

Complejidad: $???$
Código (C++):
#include <cstdio>
#include <algorithm>
using namespace std;
float C, F, X, s, g;
int main(){
 int T;
 scanf("%d",&T);
 for(int ix = 1; ix <= T; ix++){
  double gs = 2;
  double t = 0;
  double tg = 0;
  double nuevo = 0;
  double previo = 0;
  bool primerCaso =  true;
  scanf("%f%f%f", &C, &F, &X);
  while(true)
  {
   nuevo = tg;
   tg = (X / gs) + t;
   previo = tg;
   if(nuevo < previo && !primerCaso) break;
   t += C / gs;
   gs += F;
   primerCaso = false;
  }
  printf("Case #%d: %.7f\n",ix,nuevo);
 }
 return 0;
}

No hay comentarios on "Cookie Clicker Alpha (Code Jam 2014)"

Leave a Reply