Problemasysolucionespreselectivos

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 unasolución que valga la pena añadir por favor manda un mail a
luison9999@hotmail.com
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
sondenominados 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ésel 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 2006Problemas 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á unapermutació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 quecontenga 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...