Problema 91 (Mendoza, Argentina, octubre de 1993):
Dos jugadores - la computadora y Ud. - están jugando de la siguiente manera:
Ud. piensa una secuencia de 4 dígitos, no necesariamente distintos, entre 1 y 6.
La computadora (su programa) debe encontrar esta secuencia usando la información que pueda obtener de las respuestas que Ud. le dé.
Ud. contestará las preguntas de la computadora luego de que aparezca una nueva secuencia en pantalla.
Las únicas dos preguntas posibles son:
a) Cuántos dígitos son correctos pero no están en los lugares correctos?
b) Cuántos dígitos correctos están en los lugares correctos?
Ejemplo: Suponga que Ud. ha elegido la secuencia: 4655. Una manera posible de hallar esta secuencia podría ser:
COMPUTADORA SUS RESPUESTAS
1234 a) 1 b) 0
5156 a) 2 b) 1
6165 a) 1 b) 1
5625 a) 1 b) 2
5653 a) 1 b) 2
4655 a) 0 b) 4
1. Escriba un algoritmo que le permita a la computadora deducir la secuencia pensada por el jugador en, a lo sumo, 10 pasos.
2. Encuentre, si es posible, una solución en un máximo de 6 pasos.
Problema 92 (Mendoza, Argentina, octubre de 1993):
Ciertas compañías son dueñas parciales de otras compañías por haber adquirido parte de su paquete accionario; por ejemplo, Ford es dueña de un 12% de Mazda. Se dice que una compañía A controla a una compañía B cuando es cierta por lo menos una de estas tres condiciones:
a) A = B
b) A es dueña de más del 50% de B
c) A controla a k (k >=1) compañías, C(1), ..., C(k), tales que C(i) es dueña de x(i)% de B para 1 <= i <= k y x(1) + .... + x(k) > 50.
El problema a resolver es:
Dada una lista de ternas (i,,j,p) que significa que la compañía i es dueña del p% de la compañía j, hallar todos los pares (h,s) tales que la compañía h controla a la compañía s.
Escriba un programa que:
1 Lea en el archivo ASCII de entrada de datos, COMPANY.DAT, la lista de ternas (i,j,p) para el caso considerado donde i, j y son enteros positivos. Cada caso estará separado del siguiente por una línea en blanco.
2 Encuentre todos los pares (h,s) tales que la compañía h controla a la compañía s.
3 Escriba en una archivo ASCII, COMPANY.SOL, todos los pares (h,s) encontrados. Los pares (h,s) deben ser anotados en registros consecutivos y ordenados en forma creciente sobre h. Las respuestas a los distintos casos deberán separarse por una línea en blanco.
Ejemplo:
COMPANY.DAT
2 3 25
1 4 36
4 5 63
2 1 48
3 4 30
COMPANY.SOL
2 4
4 5
Problema 93 (Mendoza, Argentina, octubre de 1993):
Se superponen sobre una hoja rectangular blanca, de ancho a cm y largo b cm, N rectángulos de distintos colores que se apoyan con sus lados paralelos a los bordes de la hoja. Como resultado se verán diferentes figuras de distintos colores. El problema consiste en calcular el área de cada una de estas figuras.
El sistema de coordenadas considerado tiene el origen en el centro de la hoja y los ejes paralelos a sus bordes.
En un archivo ASCII, RECTANG.DAT, se encontrarán diferentes juegos de datos:
En la primer línea de cada juego se anotarán a, b y N separados por un espacio en blanco.
En cada una de las N líneas siguientes se encontrarán:
-las coordenadas de la posición donde se apoyó el vértice inferior izquierdo del rectángulo
-seguidas de las coordenadas de la posición donde se apoyó el vértice superior derecho
-y, a continuación, el color del rectángulo representado por un número entero entre 1 y 64. El color blanco se indicará con 1.
Los distintos juegos de datos estarán separados por un registro en blanco. El orden de los registros coincide con el orden en que fueron apoyados los rectángulos.
1. Lea el siguiente juego de datos de RECTANG.DAT
2. Calcule el área de cada una de las figuras coloreadas
3. Escriba en un archivo ASCII de salida, RECTANG.SOL, el color y el área de cada una de esas figuras tal como se muestra en el ejemplo. Las registros deberán ser ordenados en forma creciente por color. Se dejará un registro en blanco para separar las soluciones de los distintos juegos de datos.
Ejemplo:
RECTANG.DAT
1000 2000 2
0 0 500 250 15
-20 -7 0 23 15
10 6 5
-3 -2 0 2 15
4 0 5 3 15
-2.5 -1 -2 0 1
-4 -3 5 0 15
-1 -1 1 1 3
RECTANG.SOL
1 18690
15 1310
1 0.5
1 40
3 4
15 9.5
15 6
Problema 94:
Se dan 4 colores A, B, C y D y 4 cubos. Cada una de las caras de los cubos está pintada con uno de esos 4 colores. Su programa debe descubrir si es posible apilar los cubos de manera que, en cada uno de los lados de la torre resultante, cada uno de los colores aparezca una vez. Para este propósito los cubos pueden ser rotados arbitrariamente.
Escriba un programa que lea los colores de los cuatro cubos en la secuencia arriba - frente - derecha - izquierda - atrás - abajo. Si no hay solución posible, escriba "Ninguna solución" en el archivo de salida.
Si hay una solución, escriba la torre resultante en el archivo de salida. Para cada cubo, los colores de sus caras están escritos en el siguiente formato:
arriba
frente derecha izquierda atrás
abajo
Ejemplo:
B
AAAC
D
C
DABA
D
A
CBDB
C
D
BCCD
A
Variación: Encuentre todas las soluciones posibles, si es que hay alguna.
Problema 95 (Mendoza, Argentina, octubre de 1993):
New Makeup Ltd. es una importante fábrica que produce N cosméticos distintos. Mensualmente, envía a su sucursal en Mallorca un embarque de sus productos. Cada uno de los cosméticos tiene distinto tamaño y precio.
Esta semana, los estibadores del puerto de Buenos Aires han anunciado que comenzarán una huelga el lunes próximo y nadie sabe cuándo se normalizarán las actividades portuarias. New Makeup hará el sábado su próximo embarque y, por razones económicas, necesita que el valor del mismo sea máximo.
Ud. debe darle una respuesta al Gerente General de New Makeup. Para ello, en un archivo de entrada ASCII, MAKEUP.DAT, se han escrito distintos juegos de datos. En cada uno de ellos figura:
N (el número de los diferentes cosméticos)
M (la capacidad disponible en la bodega del buque)
P1 V1 (el precio y el volumen del producto 1)
P2 V2 (el precio y el volumen del producto 2)
........
PN VN (el precio y el volumen del producto N)
Donde los números N, M, Pi, Vi (1 <= i <= N) son enteros positivos.
Escriba un programa que:
1. Lea en MAKEUP.DAT el siguiente juego de datos.
2. Determine cuántas unidades de cada uno de los N productos deben ser incluidas en el embarque de manera que:
- el volumen del embarque no exceda la capacidad de la bodega del buque
- el valor del embarque sea máximo.
3. Escriba en un archivo ASCII de salida, MAKEUP.SOL:
-la cantidad de cada uno de los productos que debe ser incluida
-el valor total del embarque
-el volumen del embarque.
Las respuestas a los distintos juegos de datos deberán separarse con un registro en blanco.
Ejemplo:
MAKEUP.DAT
2
6
4 3
7 4
5
20
2 3
3 4
12 10
17 11
7 6
6
17
27 13
2 3
23 11
30 15
15 7
19 9
3
5
10 6
7 9
6 6
MAKEUP.SOL
Prod. 1 = 2
Prod. 2 = 0
Total valor= $8
Volumen = 6
Prod. 1 = 1
Prod. 2 = 0
Prod. 3 = 0
Prod. 4 = 1
Prod. 5 = 1
Total valor = $26
Volumen = 20
Prod. 1 = 0
Prod. 2 = 0
Prod. 3 = 0
Prod. 4 = 0
Prod. 5 = 1
Prod. 6 = 1
Total valor = $ 37
Volumen = 16
Prod. 1 = 0
Prod. 2 = 0
Prod. 3 = 0
Total valor = $ 0
Volumen = 0
Problema 96 (Mendoza, Argentina, octubre de 1993):
Yo soy el presidente de un Club de lectores de Ciencia Ficción. Por casualidad, hoy he descubierto un libro de CF raro y antiguo y quisiera comunicarles esta noticia a todos los miembros de club telefónicamente.
En una unidad de tiempo, un miembro del club puede hacer una llamada y dar un mensaje a sólo otro miembro del club. Cada miembro del club (exceptuándome a mí) conoce sólamente algunos de los números de teléfono de los otros miembros. Además, los miembros del club no dan los números de teléfono de otros miembros que ellos posean porque se considera una indiscreción. Mediante un programa, debe Ud. encontrar la manera más rápida, esto es, que necesite la menor cantidad de tiempo, de dar la noticia a todos los miembros del club.
Hay N miembros excluyéndome a mí. Por conveniencia, usemos los números entre 1 y N para designarlos y el 0 (cero) para designarme a mí.
Debe Ud. resolver el problema descripto para los distintos casos que serán presentados en un archivo de entrada ASCII: TELEF.DAT. Cada caso estará separado del siguiente por una línea en blanco. Los datos de cada caso figurarán así:
1ra línea: N
2da línea: lista de miembros del club cuyos números telefónicos conoce el 1
3ra línea: lista de miembros del club cuyos números telefónicos conoce el 2
...
(N+1) línea : lista de miembros del club cuyos números telefónicos conoce el N
Cada lista termina con el número 0 y el 0 aparece sólo una vez en cada lista.
En un archivo ASCII de salida, TELEF.SOL, Ud. debe grabar para cada caso considerado:
1. El tiempo mínimo M requerido para dar mi mensaje a todos los miembros del Club.
2. Para cada unidad de tiempo: quién llama a quién.
Por ejemplo, si en la tercera unidad de tiempo, 2 debe llamar a 3 y 7 debe llamar a 5, se deberá escribir en TELEF.SOL:
Time 3: 2 --> 3 7 --> 5
Ejemplo:
TELEF.DAT
7
1 2 3 4 5 6 7 0
1 2 3 4 5 6 7 0
1 2 3 4 5 6 7 0
1 2 3 4 5 6 7 0
1 2 3 4 5 6 7 0
1 2 3 4 5 6 7 0
1 2 3 4 5 6 7 0
9
2 5 7 8 9 0
1 3 6 5 0
1 5 6 0
5 6 0
1 2 3 9 0
4 7 8 0
4 5 6 0
1 7 9 0
3 4 0
TELEF.SOL
3
Time 1: 0 --> 1
Time 2: 0 --> 2 1 --> 3
Time 3: 0 --> 4 1 --> 5 2 --> 6 3 --> 7
4
Time 1: 0 --> 1
Time 2: 0 --> 2 1 --> 5
Time 3: 0 --> 3 1 --> 7 2 --> 6 5 --> 9
Time 4: 0 --> 4 1 --> 8
Problema 97 (Selección de la Delegación Olímpica, mayo de 1994):
El dinero con el que se manejan los habitantes de un país consta de n tipos de monedas con diferentes valores cada una. Supondremos que estos valores son enteros positivos y que se dispone de un número ilimitado de cada moneda.
Consideremos dos ejemplos:
Ejemplo 1:
4 tipos de monedas de valores: 1, 5, 10 y 25
Si Ud. tiene que dar un cambio de $30 lo puede hacer de varias formas:
30 monedas de $1 (30 monedas en total)
1 moneda de $25 y 1 moneda de $5 (2 monedas en total)
6 monedas de $5 (6 monedas en total)
3 monedas de $10 (3 monedas en total)
5 monedas de $1 y 1 moneda de $25 (6 monedas en total)
y muchas otras formas más.
Ejemplo 2:
5 tipos de monedas de valores 2, 10, 15, 20 y 25
Si Ud. tiene que dar un cambio de $3 no lo puede hacer usando sólo los 5 tipos de monedas de los que dispone.
El problema consiste en escribir un programa que:
1. Lea de un archivo de entrada ASCII, MONEDAS.DAT, los casos que se presentan en forma consecutiva. Los distintos casos a ser considerados estarán separados por un registro en blanco. Cada caso constará de los siguientes datos:
n {el número total de los distintos tipos de monedas disponibles, donde n es un entero positivo menor o igual que 30}
v(1) v(2) ..... v(n) {los n valores enteros positivos de cada una de ellas, separados por un espacio en blanco}
M {el monto del cambio que debe darse, donde M es un entero positivo menor que 1000}
2. Determine si es o no posible dar ese cambio con los tipos de monedas de que se dispone.
3. En caso de ser posible dar ese cambio, determine el mínimo número de monedas que se necesitan y la forma de hacerlo.
4. Escriba en un archivo de salida ASCII, MONEDAS.SOL:
a) "No es posible dar ese cambio" cuando eso es lo que sucede.
b) -el mínimo número de monedas se necesitan para dar el cambio.
-una forma de dar $M de cambio usando ese mínimo encontrado
Ejemplos:
MONEDAS.DAT
4
1 5 10 25
30
5
2 10 15 20 25
3
5
1 12 5 25 10
29
MONEDAS.SOL
Mínimo número de monedas necesario: 2
1 moneda de 25
1 moneda de 5
No es posible dar ese cambio
Mínimo número de monedas necesario: 3
2 moneda de 12
1 moneda de 5
Problema 98 (Selección de la Delegación Olímpica, mayo de 1994):
En el curso inferior del Río Paraná, la empresa Lampalagua ha establecido N puestos de alquiler de canoas y los ha numerado de 1 a N de norte a sur. En cada uno de ellos Ud. puede alquilar una canoa que debe ser devuelta en cualquiera de los puestos de la empresa río abajo (es casi imposible remar contra la corriente en esa zona). Por el alquiler de una canoa entre el puesto i y el puesto j la empresa ha establecido una tarifa. Puede suceder que esta tarifa sea mayor que la suma de una serie de alquileres más cortos en cuyo caso Ud. puede devolver la canoa en un puesto k entre i y j y continuar su viaje en una segunda canoa. Lampalagua no le cobra ningún cargo extra por los cambios de canoa que Ud. decida realizar.
El problema consiste en escribir un programa que:
1. Lea de un archivo de entrada ASCII, CANOAS.DAT, los casos que se presentan en forma consecutiva. Los distintos casos a ser considerados estarán separados por un registro en blanco. Cada caso constará de los siguientes datos:
N {el número total de puestos donde N es un entero positivo menor que 100}
v12 ... v1N {el precio del alquiler entre el puesto 1 y todos los otros separados por un espacio en blanco}
v23 ... v2N {el precio del alquiler entre el puesto 2 y todos siguientes separados por un espacio en blanco}
........................
v(N-1)N {el precio del alquiler entre el puesto N-1 y el puesto N}
i {número del puesto en que se va a iniciar el viaje}
j {número del puesto en que se quiere terminar el viaje, entendiéndose que 1 ‹ i ‹ j ‹ N}
2. Determine la forma más barata de realizar su excursión en canoa desde el puesto i al puesto j.
3. Escriba en un archivo de salida ASCII, CANOAS.SOL:
a) El costo mínimo de la excursión desde el puesto i al j.
b) Muestre el recorrido que realizará anotando los distintos puestos por los que pasará y las tarifas que se deberán abonar por cada alquiler.
Ejemplos:
CANOAS.DAT
5
7 12 15 18
2 7 16
4 7
9
1
4
7
1 2 3 2 7 9
1 2 3 2 6
4 2 5 7
6 5 3
7 2
1
2
7
CANOAS.SOL
Costo más bajo: $13
Del puesto 1 al 2: $7
Del puesto 2 al 3: $2
Del puesto 3 al 4: $4
Costo más bajo: $3
Del puesto 2 al 6: $2
Del puesto 6 al 7: $1
Problema 99 (Mendoza, Argentina, Octubre de 1993):
Ud. ha ganado un concurso organizado por una aerolínea canadiense. El premio es un pasaje gratis para recorrer Canadá, empezando por el punto más occidental visitado por esta aerolínea, viajando luego estrictamente de Oeste a Este hasta llegar al punto más oriental, volviendo luego estrictamente de Este a Oeste hasta llegar al punto de partida. Como la oficina central de la aerolínea está en la ciudad ubicada en el extremo Este, es obligatorio visitar esta ciudad para asistir a los festejos para los ganadores del concurso.
Una vez que se ha visitado una ciudad no está permitido volver a ella (salvo la ciudad de partida). Tampoco puede Ud. usar otra aerolínea u otro medio de transporte.
El problema a resolver es: dada una lista de ciudades y una lista de vuelos directos entre dos ciudades, encontrar un itinerario que visite la máxima cantidad posible de ciudades de entre las dadas (todas, si es posible) respetando las condiciones del enunciado.
Detalles:
El ingreso de datos se hará mediante un archivo ASCII, de nombre VUELOS.DAT. Cada juego de datos en el archivo consiste de:
-en la primera línea, el número N de ciudades y el número V de vuelos directos entre dos ciudades que serán listados.
-en cada una de las N líneas siguientes un nombre de ciudad, en orden de Oeste a Este (suponemos que no hay dos ciudades ubicadas en el mismo meridiano). El nombre de cada ciudad sera una cadena de, a lo sumo, 15 caracteres formada por letras del alfabeto latino y números como, por ejemplo:
AGR34 o BEL4
-en cada una de las V líneas siguientes, dos nombres de ciudades, separados por un blanco. Estos nombres deben haber aparecido en primera parte juego de datos. La aparición del par (ciudad1,ciudad2) en una línea del archivo indica que existen vuelos directos tanto de ciudad1 a ciudad2 como de ciudad2 a ciudad1.
Los distintos juegos de datos estarán separados por un registro en blanco.
Ejemplo:
VUELOS.DAT
8 10
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
Edmonton Montreal
5 5
C1
C2
C3
C4
C5
C1 C3
C2 C3
C1 C5
C2 C4
C5 C2
La solución se grabará en un archivo de salida ASCII, ITIN.SOL, donde la primera línea indicará el número M de ciudades cubiertas por el itinerario y las M líneas siguientes listarán las ciudades, una por línea, en el orden en que serán visitadas.
En el caso en que no hubiese solución deberá grabarse una línea en ITIN.SOL consignando este hecho : "No solution"
Una posible solución para el ejemplo anterior:
ITIN.DAT
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver
NO SOLUTION
Problema 100 (Mendoza, Argentina, Octubre de 1993):
Imagine que se encuentra Ud. en una reunión social de, a lo sumo, 500 invitados. El anfitrión los invita a todos a cenar. Para ello se han dispuesto muchas mesas en el salón comedor. La forma en que los invitados se sientan a las mesas es la siguiente: cualquiera que no se encuentre solo en una mesa conoce a, por lo menos, una de las personas que se encuentran en la misma mesa y a ninguna de las que se sientan en las otras mesas.
Se supone que si una persona conoce a otra persona, esta última también conoce a la primera. Ninguno de los invitados se presenta a las otras personas, lo que significa que si dos personas sentadas en una misma mesa no se conocen al sentarse a la mesa, tampoco se conocerán luego.
a) Determine cuántas mesas son necesarias y las personas que se sentarán a cada mesa.
En cada mesa hay sólamente una persona que hablará con el mozo, se la llamará el líder de la mesa. Cada persona dirá sus preferencias sobre el menú sólo a las personas que conoce. El tiempo que tarda una persona en contar sus preferencias a \cada persona que conoce se supone que es el mismo para cada persona.
b) Encuentre la persona más conveniente para ser el líder de cada mesa de manera de recibir la información de todas las personas sentadas en la misma mesa en el menor tiempo posible; muestre el líder de cada mesa y el correspondiente período de tiempo.
Luego, el anfitrión desea unificar las mesas. Para ello, llama a algunos amigos. Cada uno de ellos es presentado a los líderes de dos mesas, se unen las mesas, el amigo del anfitrión se sienta en la nueva mesa formada y se convierte en el líder de esa mesa.
c) Cuál es el orden para unir las mesas de esta manera de modo que al final todas la mesas se hayan unificado en una sola y se mantenga la condición del punto b)? Especifique el período de tiempo mínimo necesario para que el líder obtenga la información sobre todas las otras personas.
Luego de la unificación, los amigos del anfitrión se están yendo y las mesas recobran su estructura inicicial hasta el final de la cena. Cuando la cena se termina, los invitados comienzan a abandonar sus mesas
d) Determine, para cada mesa, el mínimo número de personas y el orden en el cual ellas deben irse hasta que las personas que permanezcan sentadas no se conozcan entre ellas.
Ejemplo:
MESAS.DAT
8
1 2
1 3
2 4
7 6
4 3
5 6
0 0
MESAS.SOL
Mesa 1: 1 2 3 4
Mesa 2: 5 6 7
Mesa 3: 8
Líder Mesa 1: 2
Líder Mesa 2: 6
Líder Mesa 3: 8
6 8 Nuevo Líder: 9
2 9 Nuevo Líder: 10
Período de tiempo: 3
Personas que dejan la Mesa 1: 2 3
Personas que dejan la Mesa 2: 6
Personas que dejan la Mesa 3: