Séptima Evaluación de Temas Selectos de Sistemas
Jueves 23 de junio 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 9.6.2: Jugando con ruedas (ruedas.c, ruedas.cpp
ó ruedas.java)
Considera la siguiente máquina matemática. Los
dígitos que van del 0 al 9 están impresos
consecutivamente (en la dirección de las manecillas del reloj)
en la periferia de cada rueda. Los dígitos de arriba de cada una
de las ruedas forman un entero de cuatro dígitos. Por ejemplo,
en la figura de abajo las ruedas forman el entero 8056. Cada rueda
tiene dos botones asociados con ella. Si presionas el botón
marcado con una flecha a la izquierda
se gira la rueda un dígito en la dirección de las manecillas del
reloj y si presionas el botón marcado con una flecha a la
derecha se gira la rueda un
dígito en la dirección
contraria a las manecillas del reloj. Comenzamos con una
configuración inicial de las ruedas, donde los dígitos de
la parte de arriba forman el entero S1S2S3S4.
Se te dará un conjunto de N configuraciones prohibidas Fi1Fi2Fi3Fi4
(con 1 <= i <= N) y una configuración objetivo T1T2T3T4.
Tu tarea es escribir un programa que calcule el número
mínimo de veces que se tiene que apretar un botón que se
requieren para transformar la configuración inicial en la
configuración objetivo sin pasar por ninguna
configuración prohibida.
Entrada: La primera
línea de la entrada contiene un entero M dando el número
de casos. Sigue una línea en blanco. La primera línea de
cada caso de prueba contiene la configuración inicial de las
ruedas, especificada como cuatro dígitos. Cada dos
dígitos consecutivos estarán separados por un espacio. La
siguiente línea contiene la configuración objetivo. La
tercera línea contiene un entero N dando el número de
configuraciones prohibidas. Cada una de las siguientes N líneas
contiene una configuración prohibida. Habrá una
línea en blanco entre cada dos casos de prueba consecutivos.
Salida: Para cada caso de
prueba en la entrada escribe una línea que contenga el
número mínimo de veces que se debe apretar un
botón. Si no se puede llegar a la configuración objetivo
escribe un -1.
Pista: ¿Cuál es
la gráfica que representa a este problema?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban ruedas < ruedas.ent > ruedas.txt
y comparen ruedas.txt con
ruedas.sal
Problema 9.6.3: El guía de turistas (tuguia.c, tuguia.cpp
ó tuguia.java)
El señor G trabaja como guía de turistas en Bangladesh.
Su trabajo actual es el de llevar a un grupo de turistas a una ciudad
distante. Como en todas partes, ciertos pares de ciudades están
conectados por carreteras de doble sentido. Cada par de ciudades
vecinas tiene un servicio de autobús que corre exclusivamente
entre estas dos ciudades y que usa la carretera que las une. Cada
servicio de autobús tiene un límite particular en el
número máximo de pasajeros que puede transportar. El
señor G tiene un mapa que muestra las ciudades y las rutas de
autobuses que las conectan, así como el límite de
pasajeros para cada servicio de autobús. No siempre le es
posible llevar a todos los turistas a la ciudad de destino en un solo
viaje. Por ejemplo, considera el mapa de siete ciudades mostrado abajo,
donde las líneas representan caminos y los números
escritos en cada línea indican el límite de pasajeros
asociado al servicio de autobús. Le tomará al menos cinco
viajes al señor G para llevar a 99 turistas de la ciudad 1 a la
ciudad 7, ya que el también tiene que subir al autobús
con cada grupo. La mejor ruta a tomar es la 1 - 2 - 4 - 7.
Ayúdale al señor G a encontrar la ruta por la que pueda
llevar a todos sus turistas a la ciudad de destino en el menor
número de viajes.
Entrada: La entrada contiene
uno o más casos de prueba. La primera línea de cada caso
de prueba contendrá dos enteros: N (con 0 <= N <= 100) y
R, que representan el número de ciudades y el número de
carreteras, respectivamente. Cada una de las siguientes R líneas
contendrá tres enteros C1, C2 y P donde C1
y C2 son números de ciudad y P (con P > 1) es el
número máximo de pasajeros que se pueden llevar en el
servicio de autobús entre esas dos ciudades. Los números
de ciudad son enteros en el rango 1 a N. La línea R+1
contendrá tres enteros S, D y T que representan,
respectivamente, la ciudad de origen, la ciudad de destino y el
número de turistas a ser transportados. La entrada termina con
N=R=0.
Salida: Para cada caso de
prueba en la entrada, escribe el número mínimo de viajes
requeridos para este caso en una línea aparte. Nota: Si vas a
usar los evaluadores automáticos, observa que el formato de la
salida es bastante distinto en ellos.
Pista: ¿Se podrá reducir este problema a revisar si una
cierta gráfica es conexa?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban tuguia < tuguia.ent > tuguia.txt
y comparen tuguia.txt con
tuguia.sal
