Segunda Evaluación de Temas Selectos de Sistemas
Jueves 19 de mayo de 2005 (13:00 a 15:55)
Instrucciones: Deberán
resolver dos problemas, por lo que me deberán entregar dos
códigos fuente, uno para cada problema. Cada problema se
evaluará con 10 casos de prueba y cada uno de ellos vale 1
punto. Pongan un comentario en su código indicando los dos
integrantes del equipo. La lectura se hará desde la entrada
estándar y la escritura hacia la salida estándar. En sus
pruebas, usen la redirección de entrada y salida.
Problema 3.8.3: Permutaciones comunes (percom.c, percom.cpp
ó percom.java)
Dadas dos cadenas A y B, encuentra la cadena X más larga tal que
existe una permutación de las letras de X que es una
subsecuencia de A y existe una permutación de las letras de X
que es una subsecuencia de B.
Entrada: La entrada
contendrá varios casos de prueba, cada uno de ellos consistiendo
de dos líneas consecutivas. Esto significa que las líneas
1 y 2 son un caso de prueba, las líneas 3 y 4 son otro caso de
prueba, y así sucesivamente. Cada línea contiene una
cadena de letras minúsculas, donde la primera línea de
una prueba es la cadena A y la segunda línea es la cadena B.
Cada cadena consistirá de a lo más 1000 caracteres.
Salida: Para cada caso de
prueba, escribe una línea conteniendo a X. Si varias cadenas X
satisfacen los criterios mencionados arriba, escoge la primera en orden
alfabético.
Pista: ¿Podrías
reacomodar las letras de cada palabra de modo que la permutación
común sea más visible?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban percom < percom.ent > percom.txt
y comparen percom.txt con
percom.sal
Problema 4.6.3: Cruzando un puente (puente.c, puente.cpp ó
puente.java)
Un grupo de N personas quiere cruzar un puente de noche. A lo
más dos personas pueden cruzar el puente en cualquier momento y
quienes estén cruzando el puente deben llevar una
lámpara. Sin embargo, entre las N personas sólo tienen
una lámpara, de modo que se necesita encontrar una manera de
cruzar el puente de modo que se regrese la lámpara y más
personas puedan cruzar.
Cada persona tiene una velocidad de cruce propia, y la velocidad de
quienes estén cruzando el puente queda determinada por la
velocidad del más lento de ellos. Tu trabajo es el de determinar
una estrategia que lleve a la N personas de un lado del puente al otro
en un tiempo mínimo.
Entrada: La entrada comienza
con un entero positivo en una sola línea indicando el
número de casos de prueba, seguido por una línea en
blanco. También hay una línea en blanco entre cada dos
casos de prueba consecutivos. La primera línea de cada caso
contiene el valor de N, seguido de N líneas indicando los
tiempos de cruce (en segundos) de cada una de las personas. No
habrá más de 1000 personas y nadie necesita más de
100 segundos para cruzar el puente.
Salida: Para cada caso de
prueba, la primera línea de la salida debe indicar la cantidad
total de segundos que se requieren para que las N personas crucen el
puente. Las líneas siguientes dan una estrategia para lograr
este tiempo. Cada línea contiene ya sea uno o dos enteros,
indicando que personas conforman el siguiente grupo que cruza. Cada
persona será identificada por el tiempo de cruce indicado en la
entrada. Aunque varias personas podrían tener el mismo tiempo de
cruce, esta ambigüedad no es relevante. Note que los cruces
alternan dirección, ya que es necesario regresar la
lámpara para que más personas puedan cruzar. Si hay
más de una estrategia que consuma el tiempo mínimo,
cualquiera sirve. La salida de dos casos de prueba consecutivos debe
estar separada por una línea en blanco.
Pista: ¿Serviría
de algo ordenar a las personas según su velocidad para ayudar a
determinar quienes deben cruzar el puente a cada momento?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban puente < puente.ent > puente.txt
y comparen puente.txt con
puente.sal