• Author / Uploaded
• Manuel Gómez Enríquez

Citation preview

Examenes de Preselección para la IOI 2006 Problemas y Soluciones.

Problemas y Soluciones de los Examenes de Preselección para la IOI 2006

Página 1 de 70

Examenes de Preselección para la IOI 2006 Problemas y Soluciones.

Antes de empezar... Si aún no lo has hecho, para poder entender correctamente las soluciones se recomienda leer los siguientes apuntes y de preferencia en este orden: 1.-http://www.olimpiadadeinformatica.org.mx/material%20de%20estudio/cursos/Resolver%20un% 20problema.pdf 2.-http://www.cimat.mx:88/~amor/Omi/Entrenamiento/Combinatoria/Notas_de_Combinatoria.pdf 3.-http://www.cimat.mx:88/~amor/Omi/Entrenamiento/Teoria_Numeros/Teoria_Numeros.htm http://www.olimpiadadeinformatica.org.mx/material%20de%20estudio/cursos/analisis_de_complejidad.htm 4.- http://www.olimpiadadeinformatica.org.mx/material%20de%20estudio/cursos/estructuras_de_datos.htm http://www.cimat.mx:88/~amor/Omi/Entrenamiento/Grafos/Capitulo1.htm 5.- http://ce.azc.uam.mx/profesores/franz/omi/recursion.html 6.- http://www.olimpiadadeinformatica.org.mx/material%20de%20estudio/cursos/Tecnicas_BUSQUEDAS.htm

Si aún habiendo asimilado estos apuntes encuentras una solución un tanto ambigua, algun error o una solución que valga la pena añadir por favor manda un mail a [email protected] Los problemas comienzan a partir de la página 3 y las soluciones a partir de la página 46

Página 2 de 70

Examenes de Preselección para la IOI 2006 Problemas y Soluciones.

1.- Problemas de Estructuras de Datos 1.1.- Árboles 1.2.- Laberinto 1.3.- Elecciones 1.4.- Buscaminas 1.5.- Agrupando números

Página 3 de 70

Examenes de Preselección para la IOI 2006 Problemas y Soluciones.

1.1.-Árboles (acm.uva.es) Descripción del problema: Un árbol binario es un conjunto finito de elementos que puede estar vació o contener un elemento denominado raíz del árbol y otros elementos y otros elementos divididos en dos subconjuntos separados, cada uno de los cuales es un árbol binario. Estos dos subconjuntos son denominados subárbol izquierdo y subárbol derecho del árbol original cada elemento de un árbol se denomina un nodo del árbol.  Existen tres formas comunes de recorrer un árbol binario: preorden, orden y postorden. La diferencia entre estos recorridos es el orden en que se procesan los nodos. Para cada uno de estos recorridos, el orden es el siguiente ●

Preorden: se procesa primero el nodo raíz, después el subárbol de la izquierda y por ultimo el de la derecha

●

Orden: Se procesa primero el subárbol de la izquierda, después la raíz y al final el subárbol de la derecha.

●

Postorden: Se procesa primero el subárbol de la izquierda, después el subárbol de la derecha y al final la raíz

  ●

Preorden: PLOMIAIAD

●

Orden: OLIMPIADA

 

Página 4 de 70

Examenes de Preselección para la IOI 2006 Problemas y Soluciones. ●

Postorden: OIMLIDAAP 

PROBLEMA Escribe un programa que dado los recorridos de orden y postorden de un árbol binario escriba como salida el recorrido en preorden.

Descripcion de la entrada: Tu programa deberá leer del teclado los siguientes datos, La primera linea contendrá el numero 1 ≤N≤500 que indica el numero de nodos del árbol, La segunda linea contendrá una permutación de los numero del 1 al N separados cada uno por un espacio que indican el orden de proceso de los nodos al recorrerlos en orden,En la tercera linea habrá una una permutación de los numero del 1 al N separados cada uno por un espacio que indican el orden de proceso de los nodos al recorrerlos en postorden Descripcion de la salida: Tu programa deberá escribir en pantalla una unica linea que contenga una permutación de los numeros del 1 al N que indique el orden de proceso de los nodos al recorrerlos en preorden. Ejemplo: Entrada 9 428516397 485269731 Salida 124583679 Condiciones de ejecución. Tu programa deberá ejecutarse en un tiempo máximo de 1 segundo.

Página 5 de 70

Examenes de Preselección para la IOI 2006 Problemas y Soluciones.

1.2.- Laberinto Descripción del problema: En este problema tu tomas el papel de el gran héroe Colossus tiene la misión de rescatar a la princesa omitilda de un laberinto, pero el maligno pachus quiere matar a la princesa.Lo único con lo que cuentas es con el mapa del laberinto y el tiempo en el que pachus va a llegar a la princesa, por lo que tu tienes que llegar en el menor tiempo posible a ella. El mapa consta de una cuadricula la cual tiene una 'X' en el lugar donde no puedes pasar Una 'C' donde tú te encuentras al principio, y una 'O' donde se encuentra la hermosa omitilda y una 'L' en aquellos lugares donde el campo este libre y puedas pasar. Problema Tu tarea consiste en escribir un programa que determine el menor tiempo en el que puedes llegar a rescatar a tu princesa tomando en cuenta que tu te mueves a una velocidad de un cuadro por seg. En caso de que no puedas llegar a salvarla escribirás en la pantalla un -1 en el caso contrario escribirás el tiempo en el que llegaste a ella  Descripcion de la entrada: Tu programa deberá leer del teclado los siguientes datos: En la primera línea los números 2 < M, N < 500 y T separados por un espacio donde los primeros dos son las dimensiones del laberinto y T el tiempo en que pachus llegara con la princesa. Las siguientes M líneas contendrán N caracteres que representaran el mapa. Descripcion de la salida: Tu programa deberá escribir un solo número que represente el tiempo en que llegaste ó -1 en caso de que no hayas llegado. Ejemplo:  Entrada 558 XXXXX XCLLX XXXLX XOLLX XXXXX Salida 6 Condiciones de ejecución. Tu programa deberá ejecutarse en un tiempo máximo de 1 segundo. Página 6 de 70

Examenes de Preselección para la IOI 2006 Problemas y Soluciones.

1.3.- Elecciones Descripción del problema: Imagina que nos encontramos por ahi del 6 julio del 2006 las elecciones para presidente acaban de terminar y te contrataron para hacer el conteo de votos, pero, a causa de la mala organización de los organizadores lo único que cuentas es una lista de cada voto hecho por los ciudadanos Descripcion de la entrada: Tu programa deberá leer del teclado los siguientes datos: en la primera línea el número 5