Solución a la Tarea 1: El Caracol


Existen diversas formas de resolver este problema. La más simple de ellas consiste en efectuar un ciclo que simule el movimiento del caracol dentro del agujero. Sin embargo, este procedimiento puede ser muy lento, por ejemplo, si p = 1,000,000, s = 2 y r = 1. Una forma un poco más complicada, pero que resulta en un programa mucho más rápido, es la de calcular directamente el valor de d como sigue: Sea d el número de días necesario para que el caracol salga. Como después de d-1 días el caracol no ha salido entonces se encuentra a una altura de (d-1)(s-r) medida desde el fondo del agujero. Al día siguiente sube s, y como eso es suficiente para salir entonces se cumple que (d-1)(s-r) + s >= p. Despejando, obtenemos que d >= (p-r)/(s-r). Aquí el único problema es que a veces la división es un número entero (el valor correcto de d) y a veces no (un valor ligeramente menor al correcto), pero este problema se puede resolver averiguando si s-r divide a p-r o no.

#include <stdio.h>

int main(void)
{
  long int p, s, r, d;

  scanf("%ld%ld%ld", &p, &s, &r);
  d = (p-r)/(s-r);
  if ((p-r)%(s-r) != 0)
    d = d + 1;
  printf("%ld\n", d);
  return 0;
}

También nos podemos ahorrar la decisión, escribiendo d = ((p-r)+(s-r-1))/(s-r). ¿Porqué funciona esto?

Los valores de entrada y salida empleados para la evaluación fueron los siguientes:

Entrada        Salida
10 12 2        1
10 10 1        1
10 7 4         2
10 2 1         9
9 7 1          2
14 8 5         3
159 20 9       14
2653 94 74     129
58979 459 23   136
323846 8164 7  40

Para probar su tarea en UNIX, escriban la instrucción gcc caracolNN.c -o caracol para compilar su programa, y la instrucción ./caracol para correrlo. Algunos errores comúnes fueron: (a) resolver bien el caso exacto pero no el caso inexacto (b) no usar variables de tipo long int (c) ignorar el caso en el que el caracol sale en un paso. Además, les recuerdo que sólo deben enviar el archivo .c y que éste debe tener el nombre correcto.