Archive for abril 2014

viernes, 25 de abril de 2014
por
Edit
viernes, 25 de abril de 2014

Cookie Clicker Alpha (Code Jam 2014)

por
Edit
Link al problema: Problem 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;
}
jueves, 24 de abril de 2014
por
Edit
jueves, 24 de abril de 2014

Chef and Digits (ADIGIT - CodeChef)

por
Edit
Link al problema: ADIGIT (Practice)
Link al editorial en CodeChef: ADIGIT - Editorial

Dificultad: Fácil

Problema:
Dados $N$ ($N ≤ 10^5$) dígitos y $M$ ($M ≤ 10^5$) consultas que consisten en un entero $x$ ($1 ≤ x ≤ N$), que llamaremos step (paso), imprimir el resultado de $B1 - B2$, donde:
  • $B1$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b > 0$
  • $B2$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b < 0$

 Solución:
Veamos el siguiente caso, con entrada a = 0123152397

Calculando los valores para todos los pasos tenemos lo siguiente:

En la tabla anterior he marcado dos casillas, para observar a detalle lo que sucede:
  • Para el paso 4 tenemos: $B1 = (3 -0) + (3 - 1) + (3 - 2) = 6$ y $B2 = 0$ lo cual nos da el valor de $6$
  • Para el paso 8 tenemos: $B1 = (3 - 0) + (3 - 1)+  (3 - 2) + (3 - 1) + (3 - 2) = 9$ y $B2 = (3 - 5) = - 2$, por lo tanto tenemos $B1 - B2 = 11$
Observando las ecuaciones anteriores, podemos notar que el paso 11 se compone del paso 3 en las sumas $(3 - 0) + (3 - 1)+ (3 - 2)$ más otras 3 sumas, así que ¿qué pasaría si los almacenamos para no volver a calcularlo todo? Basándonos en eso, almacenamos los resultados en otro arrelgo.

Ahora, ¿cómo es que sabemos que tenemos un valor ya calculado?, esto es sencillo de encontrar y ocurre cuando los números $a_x$ y $a_y$ son iguales. Si los calculamos de manera secuencial, es decir de 1 hasta N, estaremos garantizando que para cada paso los pasos previos ya estarían precalculados, como solo hay 10 dígitos distintos, en el peor de los casos terminaremos sumando 10 veces. Al terminar el precálculo, para cada consulta que nos hagan la respuesta será obtenida en tiempo constante

Complejidad: $O(10 * N) + O(M)$

 Código (C++):
Definiremos un arreglo A, donde A[i] es es valor de paso i-ésimo del problema y s, un arreglo de char, donde s[j] es la posición del dígito j-esimo. 
void precalc(){
 int t = 0;
 for(int step = 0; step < n; step++){
  int ans = 0;
  for(int i = step-1; i >= 0; i--){
   t = (s[step] - '0') - (s[i] - '0');
   if(t == 0){
    ans += A[i];
    A[step] = ans;
    break;
   }
   ans += abs(t);
   A[step] = ans;
  }
 }
}
Haciendo que para responder a las consultas q, solo será necesario imprimir el valor almacenado en A[q-1] 
int main(){
 scanf("%d%d",&n,&m);
 scanf("%s",s);
 precalc();
 while(m--){
  scanf("%d",&q);
  printf("%d\n", A[q-1]);
 }
 return 0;
}