Below you will find pages that utilize the taxonomy term “macs”
Posts
Solución a "Panoramas"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17 Autor: Miguel Ángel Covarrubias Fuente: Miguel Ángel Covarrubias
El problema es un Steiner tree problem (un MST pero donde sólo hay que conectar un subconjunto de nodos) pero con costo por nodo en vez de por arista. El grafo de los panoramas es un árbol más un ciclo. Para un árbol una solución es poner como raíz a $latex s_1$ y para cada $latex s_i$ marcar los nodos en su camino hacia la raíz.
Posts
Solución a "Pista"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14 Autor: Miguel Covarrubias Fuente: Codeforces
Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.
Para $latex N \le 10$ se pueden checar todas las $latex 2^N$ configuraciones de pistas. Para $latex N \le 1000$ funciona una dinámica $latex O(N^2)$, donde los estados son (posición, altura/profundidad que se lleva hasta el momento).
Posts
Solución a "Ubongo 3D"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Miguel Covarrubias Fuente: Miguel Covarrubias
La solución pone piezas de manera recursiva mientras quepan en el tablero y no se empalmen.
resuelve(pieza) si pieza > P regresa “Si” para cada rotación de la pieza para cada casilla g del tablero para cada cubo c de la pieza si al poner c sobre g, la pieza queda dentro de los primeros 2 niveles del tablero y no se empalma con otra pieza ya puesta entonces marca las posiciones de los cubos de la pieza como ocupados resuelve(pieza + 1) desmarca los cubos de la pieza Para rotar una pieza se puede rotar por $latex 0^o$, $latex 90^o$, $latex 180^o$ o $latex 270^o$ alrededor de cada eje.