Below you will find pages that utilize the taxonomy term “Examen 12”
Posts
Solución a "Mapas de bits"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12 Autor: Jorge Alberto González Martínez Fuente: Jorge Alberto González Martínez
En el problema se describen dos formas de representar un mapa de bits.
La forma bidimensional es simplemente utilizar una matriz para representar los bits. La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.
Posts
Solución a "Chilly Rapero"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12 Autor: Ethan Jiménez Vargas
La clave para resolver este problema es interpretar las palabras como nodos y los cambios entre palabras como aristas, de manera que podamos verlo todo como un grafo no dirigido. Asignamos a cada palabra un nodo y creamos las aristas entre nodos verificando alguna de las condiciones que se proponen en el enunciado del problema: si una palabra A es un prefijo o sufijo de la palabra B o la palabra A difiere con la palabra B por un solo caracter, establecemos una arista entre los nodos A y B.
Posts
Solución a "Metro"
Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12 **Autor: **Alain Acevedo Mejía
El problema en cuestión se reduce a encontrar un árbol de expansión mínima. La solución es una aplicación directa de alguno de los algoritmos existentes para ello (bien implementada), por lo que hablaré brevemente sobre una de las posibilidades y daré referencias donde puedan encontrar información más detallada.
Para encontrar el costo mínimo de unir todas las estaciones debemos encontrar el árbol de expansión mínima de la gráfica en cuestión (es decir, una subgráfica conexa que una todos los vértices de la gráfica original y cuyo peso (la suma de los costos de todas sus aristas) sea el mínimo posible (siempre es un árbol)).