Nombre Password [ Regístrate ]

Los castores (OIE 3 Fase 2 - 1999)

 

APARTADO A (tiempo máximo de resolución: 2 horas; 35% sobre el total de la prueba)

Estamos buscando castores, mejor dicho, programas que tengan un comportamiento castoril. Veamos qué queremos decir con esto. Un castor lo podemos ver como un animal que, partiendo de ningún material propio, llega a construir grandes presas gracias a su esfuerzo. Los programas con comportamiento castoril son aquellos que, partiendo de todas sus variables con valor cero, acaban teniendo un valor grande en una de sus variables. Pues bien, el objetivo de este juego es encontrar el programa que, con las características que se exponen a continuación, produzca el valor más grande (el castor que haga la presa más grande).

El lenguaje

El lenguaje con el que se pueden escribir los programas castoriles va a ser un subconjunto muy sencillo de los lenguajes que están permitidos en el concurso:

* Variables: se pueden utilizar todas las que se quieran (sin que sea necesario declararlas previamente), de nombre X1, X2, X3, X4, …, y todas de tipo entero. Se inicializan automáticamente a 0 cuando empieza la ejecución del programa.

* Sentencias: tan sólo hay asignaciones y bucles. Existen cuatro tipo de asignaciones:

Xi := Xk
Xi := Xk + 1
Xi := Xk -1
Xi := 0

donde la variable Xk puede ser la misma que Xi. Y existe un único tipo de bucle:

MIENTRAS Xi <> 0 HACER
sentencias
FIN

donde "sentencias" pueden ser asignaciones o bucles. Todas las sentencias tienen el significado habitual en los lenguajes de programación.

Ejemplo:

X1 := X1+1
X1 := X1+1
X1 := X1+1
X2 := X1
MIENTRAS X2 <> 0 HACER
X1 := X1+1
X2 := X2-1
FIN

El tamaño

Obviamente, cuantas más sentencias contenga el castor, mayor puede ser la presa máxima por él construida. Por ello, el tamaño del castor debe ser un parámetro conocido en el momento de diseñarlo. Hablaremos pues de castores de tamaño N, siendo N el número de sentencias del programa. El castor del ejemplo anterior es de tamaño 7 (seis asignaciones y un bucle).

La presa

El tamaño de la presa construida por el castor (es decir, el resultado de la ejecución del programa) se define como el valor contenido en la variable X1 después de ejecutarse la última sentencia. Que quede claro, pues, que el valor del resto de variables no cuenta. Es preciso, además, que la ejecución del programa finalice en algún momento (aunque no importa el tiempo que tarde en hacerlo). En el ejemplo anterior, la presa construida es de tamaño 6.

El objetivo

Encontrar los castores de tamaño 6, 8 y 11 que construyan las mayores presas.

La implementación

Para el castor de tamaño k, habéis de construir un fichero de nombre xxxCASk, siendo "xxx" vuestro código de concursante, que sea la traducción a C o Pascal del programa que proponéis (por ejemplo, para el castor de tamaño 6, el concursante 13 creará un fichero 013CAS6 con la extensión correspondiente). Para realizar esta traducción, debéis seguir las pautas siguientes:

* Declarar todas las variables X1, X2, ..., que hayáis utilizado en el castor.
* Inicializar a cero dichas variables al inicio del programa.
* Adaptar las instrucciones del lenguaje a las peculiaridades de C/Pascal (por ejemplo, debereis escribir "while" en vez de "MIENTRAS", deberéis poner puntos y coma, etc.).
* Al final de programa, escribir por pantalla el valor de la variable X1.
Que quede claro que ninguna de las instrucciones adicionales que surgen al traducir a C o Pascal cuentan en la longitud del programa.

Condiciones de trabajo

Las dos horas se dividen en dos partes. Durante la primera hora y media, no podéis usar el ordenador. Debéis diseñar los castores en papel. A continuación, dispondréis de media hora adicional para traducir los castores a C o Pascal.

Opcionalmente, si consideráis que ya habéis acabado la parte de diseño antes de la hora y media prevista, podéis comunicarlo a los miembros del Jurado y comenzar inmediatamente a trabajar con el ordenador, aunque debe quedar claro que el límite de media hora sigue existiendo. Esta posibilidad se contempla debido a la existencia de bonificación por acabar antes de tiempo.

Al acabar por completo este apartado, debéis comunicarlo a los miembros del Jurado, para guardar vuestra solución en diskette y empezar el apartado B.

 

APARTADO B (tiempo máximo de resolución: media hora; 15% sobre el total de la prueba)

Se pide ahora que diseñéis el castor de tamaño 12 que construya la mayor presa. En este caso, no se pide que implementéis vuestra propuesta en Pascal o C, sino que la podéis dejar expresada en el lenguaje castoril, en el fichero xxxCAS12, usando cualquier editor de textos disponible.

Podéis usar libremente el ordenador durante la resolución de este apartado. Aunque no es imprescindible que aparezcan, se valorará positivamente que, junto con el castor, se incluyan los razonamientos que llevan a su diseño.



© (2001-2008) ALGORITMIA.NET - Política de privacidad