Below you will find pages that utilize the taxonomy term “Soluciones Preselectivo 2014”
Posts
Solución a "Contraseña Binaria"
Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 7 Autor: Orlando Isay Mendoza Garcia Fuente: Christian Adan Hernández Sánchez
Podemos ayudarnos de la imagen para comprender mejor esta explicación:
En ella aparecen de forma descendente a la izquierda los números pares comenzando desde el dos, y su representación binaria a la derecha. En la parte superior aparece el valor de cada cifra en decimal.
Tomando en cuenta el límite del problema, sabemos que si sumamos $latex B(i)$ para cada par menor o igual a $latex N$, en el peor de los casos tendríamos que realizar 500,000,000,000,000 veces la función.
Posts
Solución a "Poema Equino"
Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 5 Autor: Freddy Román Cepeda Fuente: Edgar Augusto Santiago Nieves, Freddy Román Cepeda
Los límites de este problema permitían hacer una búsqueda sobre todos los estados posibles de los caballos sobre el teclado, ya que si el estado es $latex (\text{poema},\text{fila caballo}_1,\text{columna caballo}_1,\text{fila caballo}_2,\text{columna caballo}_2)$, solamente hay $latex 100 \times (4 \times 10)^2 = 160,000$ estados distintos.
Además, como el problema no pide la cantidad mínima de movimientos no hace falta hacer una BFS (búsqueda en amplitud), sino que una DFS (búsqueda en profundidad) utilizando el mismo stack del lenguaje es suficiente.
Posts
Solución a "Carretera"
Concurso: Preselectivo para la IOI 2015, Etapa 1, Examen 1 Autor: Freddy Román Cepeda Fuente: Edgar Augusto Santiago Nieves, Freddy Román Cepeda
Para obtener los puntos de la primer subtarea bastaba notar que las condiciones especificadas significan que hay dos bloques de coches yendo en diferentes sentidos que inicialmente no se intersectan y eventualmente lo harán, por lo que la respuesta simplemente es el máximo de los anchos de estos bloques.
Posts
Solución a "Suma Manhattan"
Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 1 Autor: Freddy Román Cepeda Fuente: Freddy Román Cepeda
Este problema requería manipular con cuidado la expresión que había que computar. Recordemos que nos piden computar
$latex \sum_{0 \leq i < j < N} manhattan(S_i,S_j).$
Para resolver la primer subtarea bastaba con iterar sobre todas las parejas de puntos y calcular su distancia. Esto corre en tiempo cuadrático y no es suficiente para obtener todos los puntos.
Posts
Solución a "DP Genérica"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 13 Autor: Freddy Román Cepeda Fuente: Project Euler
Podemos tratar este problema de varias maneras distintas, 3 de las cuales discutiré en esta solución.
Análisis 1 Primero, una idea que hubiera obtenido 50 puntos.
Podemos observar que el problema es equivalente a encontrar de cuántas maneras se le puede asignar un número $latex n_i$ del conjunto $latex \{0,1,2\}$ a cada potencia de 2 tal que $latex \sum_{i=0}^{\infty} n_i 2^i = x$.
Posts
Solución a "Comesolo"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: lhchavez Fuente: Félix
Este problema es especial porque es el primero en omegaUp de solo salida! Usualmente lo que debes esperar cuando te enfrentes con uno de esos problemas es que sea un problema NP que no tiene una solución rápida, y usualmente te pedirán que te aproximes lo más posible a la solución óptima. Esto significa que te vas a tener que valer de técnicas ad-hoc y heurísticas para sacar puntos.
Posts
Solución a "Colección"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 5 Autor: Alexis Cervantes / César Cepeda Fuente: Alexis Cervantes / César Cepeda
_Estructura de la solución: _¿Qué nos están pidiendo? El problema nos esta pidiendo que encontremos un subconjunto de las tarjetas tal que la suma de todos los puntajes de las tarjetas de ese subconjunto sea la maxima posible, y la suma de sus precios sea menor o igual al dinero con el que cuentas.
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.
Posts
Solución a "Bloqueo"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8 Autor: Khayyam Fuente: Khayyam
La primera observación que hay que hacer es que si todas las carreteras son bidireccionales y entre cada par de ciudades existe exactamente un camino que las conecta (usando una o mas carreteras) entonces la representación gráfica del problema es un árbol: los nodos representan las ciudades y las aristas representan las carreteras. La siguiente figura, muestra el árbol que representa el caso de prueba dado como ejemplo.
Posts
Solución a "La Venganza de Silvio"
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1 Autor: Freddy Román Cepeda Fuente: Freddy
Este problema es bastante sencillo de entender, la dificultad radica en que exponenciar un número de la manera obvia no es lo suficientemente rápido para obtener todos los puntos disponibles.
Subtarea 1 Para obtener el primer grupo de puntos, sólo basta calcular $latex N^M$ multiplicando a $latex N$ por sí mismo $latex M$ veces, teniendo cuidado de que no haya overflow.
Posts
Solución a Las Cartas del Dr. Lira
Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1 Autor: Joemmanuel Ponce Galindo Fuente: Topcoder
Básicamente lo que nos pide el problema es encontrar el número de cartas que son distintas entre la configuración que es dada como entrada y una configuración donde las cartas estén alternadas.
Cómo se explica en el problema, sólo hay 2 estados posibles en los que una carta puede estar: negro (B) y blanco (W).