EJEMPLO
PROBLEMAS DE ESTRUCTURA DE DATOS
| Pascal | C | C++ |
|
for(int i=1;i<N;i++) debe sustituirse por. int i; for(i = 1; i<N; i++)
|
inline Lucas(int n) es incorrecto, ya que no define tipo.
|
Ademas de las recomendaciones que se mencionan arriba, otra recomendacion importante es que lean cuidadosamente cual es el formato de salida del problema. En el enunciado del problema se define exactamente como debe estar formateada la salida, por ejemplo, si la salida consta de varios numeros, como deben ir, si separados por un espacio, en lineas diferentes, etc. Por favor lean la descripcion de la salida con cuidado, ya que si esta formateada de manera incorrecta sus resultados seran calificados como erroneos.
Tambien tengan MUCHO CUIDADO al seleccionar el lenguaje de compilacion de su codigo, sobre todo les recomiendo que definan correctamente si programan en C o en C++, ya que son dos lenguajes completamente diferentes, aun cuando pudiera parecer que C++ es un lenguaje que soporta todas las funciones de C, esto no es estrictamente cierto.
INSTRUCCIONES
MECÁNICA DEL EXAMEN
PROBLEMA 1:
PROBLEMA 2:
PROBLEMA 3:
PROBLEMA 4:
PROBLEMA 5:
INSTRUCCIONES
Este fue el l 1er examen de preselección por internet de la 9a Olimpiada Mexicana de Informática.(2004)
Este examen consto de 5 problemas. Cada uno de los 5 problemas tuvo un valor de 30 puntos.
MECANICA DEL EXAMEN
El examen consta de 5 problemas. Cada problema tiene un valor de 30 puntos.
Tus programas deberán leer su entrada desde el teclado, y escribir su salida a la pantalla.
PROBLEMA 1: Polinomios
Descripción del problema:
Una gran cantidad de aplicaciones de computación requieren de la manipulación de polinomios por lo que es muy importante el tener una forma de realizar operaciones con polinomios de manera eficiente.
Utilizando tus habilidades de programación deberás escribir un programa que sea capaz de realizar las operaciones de suma, resta y multiplicación de polinomios de manera eficiente y entregar un polinomio final.
Descripcion de la entrada:
Tu programa deberá leer del teclado los siguientes datos, en la primera línea el número N que indica la cantidad de polinomios. En las siguientes N líneas habrá un polinomio y un operador, estructurados de la siguiente manera: Al inicio de cada línea estará un número T que indica la cantidad de términos de el polinomio de esa línea, siguiendo al número T, separado por un espacio, estará el operador que se aplica a ese polinomio, los operadores podrán ser "+" para indicar suma, "-" para indicar resta y "*" para indicar multiplicación, por último, siguiendo al operador habrá T números enteros que indican los coeficientes (p0, p1, ..., pT-1) donde pi es el coeficiente para el término con exponente i.
El número N puede ir desde 3 hasta 100, T puede ir desde 1 hasta 20 y los coeficientes del polinomio tienen valores entre 1 y 10,000.
Para el primer polinomio del archivo puedes considerar que se efectúa la operación indicada con un polinomio cuyos coeficientes son 0 en todos los términos.
Descripcion de la salida:
Tu programa deberá escribir en la pantalla dos líneas, la primera línea debera contener el número R que indica el número de términos en el polinomio de resultado. La segunda línea deberá contener los coeficientes de cada término del polinomio separados por un espacio, comenzando por el término 0 hasta el termino R-1.
Ejemplo:
| Entrada | Salida |
| 3 3 + 3 0 1 2 * 1 2 4 - 0 0 3 5 |
4 3 6 -2 -3 |
Condiciones de ejecucion.
Tu programa debera ejecutarse en un tiempo maximo de 0.3 segundos.
PROBLEMA 2: Equilibrio de símbolos
Descripción del problema:
Si algún día requieres de hacer un compilador, requerirás de un algoritmo que revise que la sintaxis de los programas sea correcta. Se requieren de varias cosas para determinar que la sintaxis de un programa es correcta y una de ellas es determinar que todos los paréntesis, corchetes y llaves esten correctamente emparejadas.
Para que avances en el desarrollo de tu compilador, tendrás que hacer un programa que sea capaz de determinar si la sintaxis de un programa es correcta, y en caso de que no lo sea que determine la posición del primer error sintáctico.
Tu programa deberá revisar únicamente que los símbolos "(", ")", "{", "}", "[" y "]" estén correctamente emparejados, es decir, que por cada paréntesis, corchete o llave que abra exista una pareja correspondiente que cierre, y además que no se traslapen, por ejemplo el programa "a(b + c * { d / h )}" es sintácticamente incorrecto.
Descripcion de la entrada:
Tu programa deberá leer del teclado los siguientes datos: en la primera línea el número N que indica la cantidad del caracteres del programa, en la segunda línea habra N caracteres los cuales representan el programa a revisar.
El número N tendrá un valor entre 10 y 1,000,000
Descripcion de la salida:
Tu programa deberá escribir en la pantalla únicamente una línea con un número que indica la posición del primer error sintactico, en el caso de que el programa no tenga errores de sintaxis tu programa deberá escribir un 0 (cero) como respuesta.
Ejemplo:
| Entrada | Salida |
| 20 a(b + c * { d / h )} |
19
|
Condiciones de ejecucion.
Tu programa deberá ejecutarse en un tiempo maximo de 0.3 segundos.
PROBLEMA 3: Arboles de búsqueda
Descripción del problema:
Una de las estructuras de datos mas comunes es el árbol binario de búsqueda, éste árbol además de ser binario como su nombre lo indica, tiene la peculiaridad de que está ordenado para facilitar la búsqueda de datos. Su orden es el siguiente: Supongamos que se está buscando el valor x, para encontrarlo se compara x con el valor de la raíz del árbol, si el valor en la raíz es x entonces ya terminamos, si el valor en la raíz es menor que x entonces nos vamos al hijo de la derecha, si el valor en la raíz es mayor que x entonces nos vamos al hijo de la izquierda, si se llega al final de una rama del árbol sin haber encontrado el valor, quiere decir que dicho valor no se encuentra en el árbol.
Sin embargo para que el citado árbol de búsqueda funcione, es necsario que los datos hayan sido insertados en el árbol cumpliendo con lo anterior, es decir, para insertar un valor, se compara con la raíz, si es mayor que el valor de la raíz entonces se avanza hacia su hijo de la derecha y se vuelve a comparar, si es menor se avanza hacia su hijo de la izquierda, de este modo se continúa comparando hasta que se llegue al final de una rama del árbol y en esa posición se inserta el nuevo dato. Si un dato ya se encontraba en el árbol, no es necesario insertarlo.
Deberás escribir un programa que comience con un árbol binario de búsqueda vacío y vaya tomando datos e insertándolos de manera correcta. Una vez que haya terminado de insertar todos los datos deberá escribir el contenido de los nodos en preorden, orden y postorden. Si no sabes lo que son estos recorridos revisa la sección de material de estudio en la página de la olimpiada.
Descripcion de la entrada:
Tu programa deberá leer del teclado los siguientes datos: En la primera línea el número N que indica la cantidad de datos que tendrás que insertar en el árbol, en la siguiente línea habrá N números enteros separados cada uno por un espacio.
El número N tendrá valores entre 3 y 10,000;
Descripcion de la salida:
Tu programa deberá escribir tres líneas, en la primera línea deberá escribir el recorrido en preorden del arbol, escribiendo el número contenido en cada nodo y separandolo del siguiente por un espacio, en la segunda línea deberá escribir el recorrido en orden y por último en la tercera línea debera escribir el recorrido en postorden del árbol.
Ejemplo:
| Entrada | Salida |
| 5 5 3 2 24 11 |
5 3 2 24 11 2 3 5 11 24 2 3 11 24 5 |
Condiciones de ejecucion.
Tu programa debera ejecutarse en un tiempo maximo de 0.3 segundos.
Descripción del problema:
Todos hemos alguna vez utilizado el famoso método de "De tin marin, de do pingue ... " para seleccionar al que "le tocaba" en algún juego. Para este problema tendrás que escribir un programa que simule al "Tin marin" pero con reglas ligeramente distintas.
El juego comienza asi, al inicio del mismo, todos los jugadores seleccionan un número distinto que puede ir del 1 al 1,000,000; una vez que todos los jugadores han seleccionado su número se inicia por el jugador 1 y se cuentan N lugares, donde N es el número seleccionado por el jugador 1, si se llega al final de los jugadores, se vuelve a comenzar por el jugador 1. Una vez que han sido contados los N lugares, el jugador en el que terminó la cuenta, sale del circulo. A continuación se cuentan M lugares comenzando por el jugador que estaba inmediatamente después del que salió, donde M es el número seleccionado inicialmente por el jugador que salió.
El último jugador que quede dentro del círculo es el ganador.
Deberás escribir un programa que dados los números iniciales que seleccionó cada jugador determine que jugador es el último que queda en el círculo.
Descripcion de la entrada:
Tu programa deberá leer del teclado los siguientes datos: En la primera línea el número J que indica la cantidad de jugadores, en la segunda línea habrá J números enteros separados por un espacio cada uno que indican los números seleccionados al inicio del juego por cada uno de los jugadores.
El número de jugadores podrá ir de 2 a 10,000
Descripcion de la salida:
Tu programa deberá escribir en la pantalla un único número que indique el número del jugador ganador.
Ejemplo:
| Entrada | Salida |
| 4 5 1 7 2 |
1 |
Condiciones de ejecucion.
Tu programa debera ejecutarse en un tiempo maximo de 0.3 segundos.
Descripción del problema:
Acabas de abrir una empresa de paquetería. Todos los días por la mañana recibes una cantidad paquetes con sus respectivas fechas de envío, desgraciadamente no cuentas aún con suficiente infraestructura y solamente puedes enviar 3 paquetes cada día, además por políticas de la empresa no puedes enviar ningún paquete antes de su fecha de envío. Si por cuestión de infraestructura no pudiste entregar un paquete a tiempo, deberás tratar de entregarlo lo más rápido posible.
Debes escribir un programa que dado un calendario de como fueron llegando los paquetes con sus respectivas fechas de envío determine cual la mejor forma de entregarlos de modo que la suma total de los días de retraso sea la mínima posible. Por cada paquete que se retrase un día en su fecha de entrega, la suma total aumentará en uno.
Descripcion de la entrada:
Tu programa debera leer del teclado los siguientes datos, en la primera linea el numero D que indica la cantidad de días que se te darán de calendario como entrada, a continuación habra D bloques, cada uno describiendo los paquetes que llegan ese día, cada bloque estará conformado de dos líneas con la siguiente estructura: en la primer línea del bloque está la cantidad P de paquetes que llegaron ese día, en la segunda línea habrá P números separados cada uno por un espacio, el número i-esimo representa el día en el que se deberá entregar el paquete i. Si un día llegan 0 paquetes el bloque descriptor de ese día no contendrá segunda línea.
El número D puede ir de 1 hasta 1000. El número P puede ir de 0 hasta 1000. El número i puede ir de 1 hasta 1,000,000.
El primer día de la entrada se considera el día 1 y de ahí se toman los días de forma consecutiva.
Si se recibe un paquete en el día d puede enviarse ese mismo día si la infraestructura lo permite.
Descripcion de la salida:
Tu programa debera escribir en la pantalla de la PC el numero total de días de retraso en la entrega
Ejemplo:
| Entrada | Salida |
| 3 7 3 1 2 3 1 3 4 0 5 3 5 6 5 3 |
2 |
Condiciones de ejecucion.
Tu programa debera ejecutarse en un tiempo maximo de 0.3 segundos.
