Sexta Evaluación de Temas Selectos de Sistemas
Jueves 17 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 8.6.1: Pequeños alfiles (alfils.c, alfils.cpp
ó alfils.java)
Un alfil es una pieza que se usa en el juego de ajedrez que
sólamente se puede mover en diagonal desde su posición
actual. Dos alfiles se atacan el uno al otro si uno de ellos
está en el camino del otro. En la figura de abajo, los cuadros
grises representan las posiciones alcanzables por el alfil A1 desde su
posición actual. Los alfiles A1 y A2 están
atacándose el uno al otro, mientras que A1 y A3 no lo
están, de la misma forma que A2 y A3 tampoco lo están.
Dados nos
números N y K, encuentre el número de formas en las que
se pueden poner K alfiles en un tablero de ajedrez de N por N de modo
que ninguna pareja de ellos se ataquen el uno al otro.
Entrada: La entrada
contendrá múltiples casos de prueba. Cada caso de prueba
ocupa una sóla línea de la entrada y contiene dos enteros
N y K, con 1 <= N <= 8 y 0 <= K <= N2. Un caso
de prueba que contenga dos ceros termina la entrada.
Salida: Para cada caso de
prueba, escribe una línea que contiene el número total de
formas en las que se puede poner la cantidad dada de alfiles en el
tablero de ajedrez del tamaño dado de modo que ninguna pareja de
ellos se ataquen el uno al otro. Puedes suponer que este número
será siempre menor que 1015.
Pistas: ¿De qué
forma se deberá modificar la solución al problema de las
ocho reinas para resolver el problema de los alfiles?
¿Servirá de algo separar los problemas de colocar los
alfiles blancos y de colocar los alfiles negros?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban alfils < alfils.ent > alfils.txt
y comparen alfils.txt con
alfils.sal
Problema 8.6.3: Cola criminal (colacr.c, colacr.cpp ó
colacr.java)
Considera una cola con N personas, todas ellas de altura distinta. Una
persona puede ver hacia la izquierda de la cola si ella es más
alta que todas las personas a su izquierda; de lo contrario su
visión está bloqueada. De forma similar, una persona
puede ver hacia la derecha de la cola si ella es más alta que
todas las personas a su derecha; de lo contrario su visión
está
bloqueada. Se ha cometido un crimen, donde una persona que está
a la izquierda
de la cola ha matado a una persona que estaba a la derecha de la cola
utilizando
un bumerán. Exactamente P personas en la cola podían ver
hacia la izquierda y exactamente R personas en la cola podían
ver hacia la derecha, y por lo tanto podrían haber sido
testigos del crimen. El abogado defensor te ha contratado para que
encuentres
cuántas permutaciones de N personas tienen esta propiedad para P
y R dados.
Entrada: La entrada consiste de
T casos de prueba, donde T está en la primera línea de la
entrada y 1 <= T <= 10,000. Cada caso de prueba consiste de una
línea que contiene tres enteros. El primer entero N indica el
número de personas en la cola (1 <= N <= 13). El segundo
entero P corresponde con el número de personas que podían
ver a la izquierda. El tercer entero R corresponde con el número
de personas que podían ver a la derecha.
Salida: Para cada caso de
prueba, escribe el número de permutaciones de N personas donde P
personas pueden ver a la izquierda y R personas pueden ver a la derecha.
Pistas: ¿Cómo
podríamos representar la solución para una
búsqueda eficiente? ¿Nos conviene construir las
permutaciones ó identificar los subconjuntos de personas que
podían ver?
Ejemplos: Entrada
y salida. Para usar este ejemplo, escriban colacr < colacr.ent > colacr.txt
y comparen colacr.txt con
colacr.sal