Nesecito ayuda sobre unos problemas que no logro resolver y nesecito que sea entre lo posible antes de 60 horas.
1er Problemas.
Este a˜no el examen de Dise˜no y An´alisis de Algoritmos ser´a oral: a cada equipo,
de tres estudiantes, se asignan tres problemas que debe resolver y luego defender
su soluci´on ante los profesores. Estos ´ultimos han reunido un total de 3n
problemas (incluyendo este) donde n es el n´umero de equipos. Los problemas
est´an clasificados seg´un el tema que se eval´ua en ellos, por ejemplo: Cotas M´ınimas,
Algoritmos Golosos, Programaci´on Din´amica, NP-Completitud, etc´etera.
Tal clasificaci´on no es necesariamente excluyente, o sea, puede que exista un
problema en que se eval´uen conocimientos y habilidades del estudiante sobre
m´as de un tema. Por otra parte, cada problema tiene asociado un n´umero que
indica su grado de dificultad. Los profesores deben realizar una distribuci´on de
los problemas para los diferentes equipos de la manera m´as balanceada posible
y garantizando que a un mismo equipo no se eval´ue el mismo tema con dos
problemas diferentes. En este punto lo desbalanceada que es una distribuci´on se
mide como la diferencia entre el m´aximo y el m´ınimo por todos los equipos de la
complejidad promedio de los problemas asignados, y la complejidad promedio
es el promedio del grado de complejidad de los problemas.
Donde el equipo de mayor complejidad promedio es el 2do y el de menor es el
3ro, por lo que la diferencia que mide el desbalance es 3. Dise˜ne un algoritmo
que realice una distribuci´on lo m´as balanceada posible bajo las restricciones
anteriores.
2do Problema
Acr´ostico
Originalemente el t´ermino acr´ostico se refer´ıa a una composici´on po´etica en que
las letras iniciales, medias o finales de cada verso, le´ıdas verticalmente forman 1
un vocablo. M´as tarde, el t´ermino se ha extendido a cualquier forma de escribir
palabras entrelazadas en direcci´on horizontal o vertical, pero en un solo sentido:
de izquierda a derecha o de arriba a abajo. Por ejemplo, el siguiente es un
acr´ostico:
Es una especie de matriz donde ubicas palabras entrelazadas con la condicion de que todas tienen que estar etrelazadas y en las letras que se crusen deben serr las mismas.
El tama˜no de un acr´ostico es el m´aximo entre el n´umero de l´ıneas y columnas
que ocupa; en el ejemplo hay 10 columnas y 10 filas, por lo que el tama˜no es 10.
N´otese que para cualquier lista de palabras no necesariamente existe un acr´ostico.
Por ejemplo, para las palabras rojo y azul no existe ning´un acr´ostico.
Dise˜ne un algoritmo que dada una lista de palabras determine si existe un
acr´ostico, y en caso positivo, construya un acr´ostico de tama˜no m´ınimo para las
palabras de la lista.
Offline