Octava Evaluación de Temas Selectos de Sistemas
Jueves 30 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 13.6.5: Pastel de cumpleaños (pastel.c, pastel.cpp
ó pastel.java)
Lucy y Lily son gemelas. Hoy es su cumpleaños, así que su
madre les compra un pastel de cumpleaños. Hay 2N cerezas en el
pastel, donde 1 <= N <= 50. Su madre quiere cortar el pastel en
dos mitades con un solo corte rectilíneo pasando por el centro
de modo que cada gemela tenga tanto la misma cantidad de pastel como el
mismo número de cerezas. ¿Podrías ayudarle? El
pastel tiene radio 100 y su centro está localizado en (0, 0).
Las coordenadas de cada cereza están dadas por dos enteros (x,
y). Debes dar una línea en la forma Ax + By = 0, donde A y B son
enteros en el intervalo [-500, 500]. No se permite que ninguna cereza
esté en la línea de corte. Habrá al menos una
solución para cada caso de prueba.
Entrada: La entrada contiene
varios casos de prueba. La primera línea de cada caso contiene
el entero N. Esto se sigue con 2N líneas, donde cada
línea contiene las coordenadas (x, y) de una cereza con un
espacio entre ellas. La entrada termina cuando N = 0.
Salida: Para cada caso de
prueba, escribe una línea conteniendo a A y a B con un espacio
entre ellas. Si hay varias soluciones, cualquiera es buena.
Pistas: Siempre existe una
solución para este problema si se elimina el requerimiento de
que la línea de corte tenga coordenadas enteras.
¿Podrías probarlo? ¿Habrá alguna
solución más eficiente que la de intentar todos los pares
posibles A y B?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban pastel < pastel.ent > pastel.txt
y comparen pastel.txt con
pastel.sal
Problema 13.6.8: ¿Qué tan grande es? (grande.c,
grande.cpp
ó grande.java)
Ian irá a California y tiene que empacar sus cosas, incluyendo
su colección de círculos. Dado un conjunto de
círculos, tu programa debe encontrar la caja rectangular
más pequeña en la que quepan. Todos los círculos
deben tocar el fondo de la caja. La figura de abajo muestra un
empaquetamiento aceptable para un conjunto de círculos, aunque
no es necesariamente un empaquetamiento óptimo para estos
círculos en particular. En un caso ideal, todo círculo
debería tocar al menos alguno otro, pero probablemente ya te
habías dado cuenta de esto.
Entrada: La primera
línea de la entrada contiene un entero positivo N <= 50, que
indica el número de casos de prueba que siguen. Las siguientes N
líneas contienen una serie de números separados por
espacios. El primer número de cada una de estas líneas es
un entero positivo M <= 8, que indica cuántos otros
números aparecerán en esa línea. Los siguientes M
números en la línea son los radios de los círculos
que se deben empacar en una sola caja. Estos números no son
necesariamente enteros.
Salida: Para cada caso de
prueba, tu programa debe escribir el tamaño (horizontal) del
rectángulo más pequeño en el que se pueden empacar
los círculos. Cada caso debe ser escrito en una línea
separada por sí mismo, con tres dígitos decimales. No
escribas ceros al principio de un número a menos que éste
sea menor que 1, por ejemplo 0.543.
Pistas: ¿Será
mejor ordenar los círculos del mayor al menor o intercalarlos?
¿O será que el orden nunca importa?
¿Servirá de algo hacer búsqueda con retroceso en
este problema?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban grande < grande.ent > grande.txt
y comparen grande.txt con
grande.sal
