Saltar a contenido

Ejercicios · Refuerzo PUJ 14 de noviembre

Actividades para trabajar en el navegador los temas de la sesión. Las tres primeras corren el código de los problemas que se resuelven en clase, y las de invariantes acompañan a la hora de lógica. Las de colas de prioridad, bisección y dividir y vencerás van con los problemas propuestos.

Cómo se plantea la solución

repartir textos entre empleados

Bisección sobre la respuesta: preguntas de planteamiento, y después se mueven lo y hi sobre la fila de textos hasta 1700.

una rejilla con zonas prohibidas

Se marcan las zonas con la distancia euclidiana y se avanza el frente de la cola sobre el tablero, decidiendo qué vecinas entran.

dos colores

Se escoge el color de cada nodo con la pila de llamadas a la vista, hasta ver el choque en el triángulo y el pedazo que queda sin mirar.

UVa 10004, Bicoloring

El código de dos colores sobre los casos del juez: antes de cada nodo se predice su color o el choque, y al final de cada caso la salida, BICOLORABLE. o NOT BICOLORABLE.

UVa 11080, Place the Guards

Los guardias son uno de los dos colores de cada pedazo: se pinta cada pedazo, se escoge cuántos guardias aporta y al final la salida, que es -1 si algún pedazo choca.

Recorridos: tipos de arista y ciclos

los tipos de arista

Antes de que la profundidad pinte cada arista hay que predecir si es de árbol, de retroceso, de avance o cruzada, en un grafo dirigido y en el mismo sin flechas.

kahn

Los grados de entrada y la cola, paso a paso.

ciclo

La cola se vacía antes de tiempo: cuántos nodos alcanzan a salir y quiénes se quedan.

tareas

UVa 10305, Ordering Tasks, con otra instancia: la lectura, la lista de adyacencia que construye y el orden que imprime Kahn.

Invariantes de ciclo

sumar

La suma de un arreglo: predecir qué devuelve, mirar la traza de estados y encontrar los invariantes \(I_0\) e \(I_1\), que se demuestran con inicialización, estabilidad y terminación.

credito

UVa 11078: los invariantes del mayor y de mejor, con el mayor llamado maximo. Al elegir un candidato errado, la traza marca en rojo el chequeo donde falla.

mayores

El mayor y el segundo mayor en un recorrido: ninguno de los dos invariantes se demuestra por separado, y un arreglo con todos los valores iguales decide cómo escribir el del segundo.

tramo

UVa 507 sin el desempate: los invariantes de suma y de mejor. Trae la respuesta del ejercicio en papel, así que va después de intentarlo.

Colas de prioridad

priority-queue

Lo que imprime un programa con push, top y pop, y un comparador que deja el menor arriba. Es la operación de la que depende UVa 1203, uno de los propuestos.

Bisección: cuando la función ya viene dada

resolver un problema de juez

UVa 10341 atacado en diez tarjetas que se abren una tras otra: entender la entrada, nombrar la función, demostrar término a término que decrece, mirar el rango, decidir si la solución existe, fijar la tolerancia y recién ahí escribir código. La tarjeta de la monotonía es la que decide el problema.

biseccion

La bisección sobre una función continua, con tres funciones distintas, para ver qué pasa cuando el objetivo queda fuera del rango.

Bisección sobre la respuesta

buscar

La búsqueda binaria sobre un arreglo ordenado, división por división. UVa 11413 aplica la misma idea sobre las capacidades posibles.

Dividir y vencerás

contar parejas fuera de orden

UVa 10810. Se predice el número de parejas sobre un arreglo chico y después corre el código de la sesión, con las dos posiciones de la mezcla marcadas y el aporte de cada elemento que sale de la derecha.

mezclar

La mezcla sola, escritura por escritura, con su pareja de invariantes. Es el paso de combinación del ejercicio anterior, sin el conteo encima.

ordenar

El ordenamiento por mezcla completo, con el árbol de llamadas a la vista: de cuánto trabajo hay en cada nivel y por qué hay logarítmicos niveles.