En este repositorio subo los codigos fuente de los ejercicios que voy haciendo de practica para la OIA.
Ademas debajo doy una breve descripcion del problema para cada codigo y donde puede encontrarse el enunciado completo
Este es un problema del nacional del 2019, Nivel 3 Problema 2.
En resumen en el problema se pasa un mapa estilo laberinto con "paredes" y entradas; y se pide que a medida que se ingresan nuevos obstaculos al mapa se digan a cuantos lugares se puede llegar.
Devido a la tecnica usada para recorrer el tiempo en forma inversa, en el peor caso se tienen varias componentes conexas al principio del algoritmo y se deben optimizar su analisis para evitar ir una por una que terminaria resultando en una complejidad de O(MxNxP)
Para evitar esto se usa el mismo union find pero uniendo ademas cada set a un set 0, que nos sirve como set globalizador y de donde podemos saber la suma de todas las componentes conexas en todo momento de forma rapida.
Este problema se puede encontrar en el juez de la OIA.
En este problema se pasan bloques con tamaños x, y. Los bloques tienen la propiedad de que se pueden apilar uno encima del otro si el bloque de abajo contiene al bloque de arriba.
De esta forma se pide que para un conjunto de bloques se diga cual es la minima cantidad de torres que se debe realizar. Siendo las torres, un bloque de cimiento con bloques arriba.
Este problema se puede encontrar en el juez de la OIA.
En este problema se pasa un mapa estilo laberinto y se pide que empezando en la posicion 1, 1 se llegue a la salida en n, n.
Como restriccion, solo se pueden realizar movimientos de caballo, alfil y torre que tienen costes asociados 1, 2 y 3 respectivamente.
Ademas la solucion devuelta debe minimizar las jugadas y los costes.