Problema 61:
El cartero de una zona campestre debe entregar cartas en N de las casas de la región. Para ello, desea armarse un recorrido que le permita entregar todas las cartas y regresar a su oficina, queriendo que el trayecto entre dos casas consecutivas sea siempre recto. Como le gusta pasear pretende, además, que el recorrido no se "corte" a sí mismo. El problema consiste en escribir un programa que permita el ingreso de las coordenadas (X,Y) de cada una de las N casas y de la Oficina de Correos y que, si existe, encuentre un recorrido que satisfaga los deseos del cartero emitiendo finalmente una lista de las casas en el orden en que deben ser visitadas.
ENTRADA:
Ingresar y validar:
N: el número de casas que deben ser visitadas.
(X(i),Y(i)), 1 < i < N: las coordenadas de los puntos correspondientes a cada una de las casas.
(X(N+1),Y(N+1)): las coordenadas correspondientes a la Oficina de Correos.
SALIDA:
- una lista de las coordenadas de los puntos del recorrido, que comience y termine con las coordenadas de la Oficina de Correos, respetando el orden en que deben ser visitados.
Ejemplo: N = 8
Coordenadas de las casas:(1,4); (2,-2); (-2,-2); (3,2); (2,1); (0,0); (-1,1); (0,-0.5)
Oficina de Correos: (1,0)
Una posible solución es:(1,0); (2,1); (3,2); (1,4); (-1,1); (0,0); (-2,-2); (0,-0.5); (2,-2); (1,0)
Otra solución posible es:(1,0); (0,0); (-1,1); (0,-0.5); (-2,-2); (2,-2); (3,2); (2,1); (1,4); (1,0)
Problema 62:
La fábrica LEOP de lentes ópticos está equipada con un sistema computarizado para detectar defectos en las planchas rectangulares de vidrio que usan como materia prima. Lamentablemente estas planchas siempre tienen "burbujas". Cuando el sistema analiza cada plancha revela los siguientes datos:
- L y A: largo y ancho de la plancha, respectivamente
- N: el número total de burbujas
- (X(i),Y(i)) las coordenadas del centro de la i-ésima burbuja (1 < i < n)
- R(i) el radio de la i-ésima burbuja
En el proceso de fabricación de los lentes se plantea, para cada plancha de vidrio, el problema de encontrar el círculo de máximo radio que no contenga ninguna burbuja. La herramienta mecánica que corta los lentes circulares debe ser informada de las coordenadas (M,N) del centro de ese círculo máximo y se le debe dar un número entero positivo R de manera que fije el radio como R.D donde D es un número positivo pequeño fijo que depende sólo de la herramienta. Si bien la profundidad a que se encuentran las burbujas no es suministrada por el sistema, el grosor de los lentes es aproximadamente igual al grosor de las planchas.
Escriba un programa para resolver este problema y calcule el centro de los lentes y el número R en los siguientes casos:
1- A = 14; L = 14; D = 0.01
N = 3
X(1) = 8; Y(1) = 8; R(1) = 1
X(2) = 2; Y(2) = 7; R(2) = 1
X(3) = 13; Y(3) = 11; R(3) = 0.7
2- A = 16; L = 10; D = 0.01
N = 4
X(1) = 1; Y(1) = 3; R(1) = 1
X(2) = 5; Y(2) = 7; R(2) = 1
X(3) = 9; Y(3) = 3; R(3) = 1
X(4) = 13; Y(4) = 7; R(4) = 1
Problema 63: (Este problema fue propuesto por la Argentina en la IOI 91 realizada en Atenas en mayo de 1991)
Un granjero tiene, próximos a su casa, una rara variedad de cipreses que desea preservar por su antigüedad. Con cuidado, ha anotado la ubicación de cada uno de los árboles y ha decidido cercarlos con alambre formando un polígono que contenga a todos los árboles, pero, para reducir sus costos, necesita minimizar la cantidad de alambre empleado. El problema consiste en:
A) encontrar los árboles que servirán como vértices del polígono
B) la longitud (mínima) de alambre que se usará.
C) determinar si la casa del granjero queda dentro o fuera del cerco
D) determinar la superficie de la granja que quedará cercada
ENTRADA:
Ingresar y validar:
N: el número de cipreses que deben ser preservados.
(X(i),Y(i)), 1 < i < N: las coordenadas de los puntos correspondientes a cada uno de los árboles
SALIDA:
- una secuencia de M puntos (2 < M < N) árboles que servirán como vértices del polígono de manera que para cada i > 2 el segmento que une (X(i-1),Y(i-1)) con (X(i),Y(i)) forma parte del perímetro del polígono.
- la longitud aproximada del alambre que se empleará.
Ejemplo: N = 8
1ø
2ø 6ø 5ø
3ø 8ø
7ø 4ø
el polígono en cuestión será el determinado por los siguientes árboles:
7, 4, 5, 1, 2
Problema 64:
Dos chicos, A y B, se entretienen con el siguiente juego:
Se tiene una caja que contiene N pelotitas iguales; el primer jugador toma todas las que quiera con la salvedad de que no puede tomarlas todas, a partir de la primera jugada los jugadores se alternan tomando pelotitas de la caja pero no pueden tomar más del doble de lo que ha tomado el jugador precedente. El ganador es aquél que, en su turno, deja vacía la caja. Por ejemplo, para N = 11:
Jugador Máximo que puede tomar Toma Quedan
A: 10 3 8
B: 6 1 7
A: 2 2 5
B: 4 1 4
A: 2 1 3
B: 2 1 2
A: 2 2 0
El jugador A es el ganador!!!
Cuál es la mejor jugada para el primer jugador si hay inicialmente 1000 pelotitas en la caja? Se trata entonces de escribir un programa de forma tal que la computadora juegue por uno de los dos jugadores de manera optima.
Problema 65:
Se quiere dibujar un diagrama de palabras cruzadas a partir de una matriz dada de "ceros y unos". El 1 indica un casillero "blanco" y el 0 indica un casillero "negro". Se trata entonces de escribir un programa que:
1.-permita el ingreso desde el teclado de N y de una matriz NxN de ceros y unos.
2.-muestre en pantalla el diagrama de palabras cruzadas con los casilleros apropiados numerados para las palabras "horizontales" y las "verticales". Un casillero deber ser numerado si es un casillero en blanco y si ocurre, por lo menos, una de las siguientes situaciones:
a) el casillero por debajo de él es blanco y no hay un casillero en blanco inmediatamente sobre él.
b) no hay un casillero blanco a su izquierda y el casillero a su derecha es blanco. Además, los casilleros negros que están sobre los bordes no deben ser impresos.
El siguiente método debe usarse para mostrar el diagrama: Cada casillero del crucigrama corresponde a 5 columnas y 3 filas de la pantalla. Estas 15 posiciones deben ser "llenadas" de la siguiente manera:
Casillero negro Casillero blanco
+ + + + + + + + + + + + + + + + + + + + + +
Casillero blanco numerado
n +
+
+ + + + +
cuidando de "cerrar" todos los casilleros.
Damos a continuación una matriz de ceros y unos de 4x4 y su correspondiente crucigrama:
1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0
Crucigrama en pantalla:
+ + + + + + + + + + +
+ 1 + +
+ + +
+ + + + + + + + + + + + + + + + + + + + +
+ 2 + + + + + + + 3 +
+ + + + + + + + +
+ + + + + + + + + + + + + + + + + + + + +
+ + + + + + + 4 + +
+ + + + + + + + +
+ + + + + + + + + + + + + + + + + + + + +
+ 5 + + + + + + +
+ + + + + + + +
+ + + + + + + + + + + + + + + +
Problema 66:
Para la función f:[0,2] --> R definida por:
f(x) = 3x3 - 20x2 + 29x + 10
se sabe lo siguiente:
a) Existe un xM en el intervalo [0,2] tal que:
f(xM) > f(x) para todo x del intervalo [0,2]
b) f crece estrictamente en el intervalo [0, xM]
f(x1) < f(x2) si 0 < x1 < x2 <xM
c) f decrece estrictamente en el intervalo [xM,2]
f(x1) > f(x2) si xM < x1 < x2 <2
Se trata entonces de escribir un programa que:
- permita el ingreso desde el teclado de un número r tal que 0 < r < 1
- determine un punto xr del intervalo [0,2] tal que
xr - r < xM < xr + r
Problema 67:
Se tienen N libros, numerados de 1 a N, y dos personas, A y B, que quieren leerlos. Con el número entero positivo A[i] (resp. B[i]) se indican las horas que necesita el lector A (resp. B) para leer el libro i (1 < i < N). Ambas personas comienzan a leer en el momento 0. En cualquier instante a partir de allí, cada una de ellas puede, a lo sumo, estar leyendo un libro y, además, A y B no pueden leer el mismo libro al mismo tiempo. Cada lector puede interrumpir la lectura de un libro luego de un número entero de horas y recomenzarla más tarde en el lugar en que la interrumpió; durante la interrupción puede comenzar, seguir o terminar la lectura de cualquier otro libro.
Se da también un entero K ( 0 < K <N) y se supone que los libros están numerados de manera que los primeros K libros forman el prestigioso tratado "Arte y ciencia en computación". En el caso en que K > 2, ninguno de los dos lectores puede comenzar la lectura del libro J (2 < J < K) hasta que el libro J-1 haya sido leído POR AMBOS.
Se trata entonces de escribir un programa que:
A.- Lea de un archivo de texto ASCII, LIBROS.DAT, los valores para N, K, A[i], B[i]
(1 < i < N) validando la información, hasta que el archivo haya sido leído completamente. El archivo tendrá la siguiente estructura:
N K
A[1] B[1]
..................
A[N] B[N]
Cada caso estará separado del siguiente por un registro en blanco.
B.- Determine si existe o no un entero M (1 < M < N) de manera que:
A[M] > B[1] + ... + B[M-1] + B[M+1] + ... + B[N]
y
B[M] > A[1] + ... + A[M-1] + A[M+1] + ... + A[N]
mostrando en pantalla y grabando en un archivo de salida ASCII, SOL.SOL, un mensaje del tipo "NO existe el M buscado" o bien "El M buscado es igual a xxx".
C.- Muestre en pantalla y grabe en el archivo de salida SOL.SOL, un cronograma de lectura para A y otro para B que respeten las restricciones impuestas de manera que ambos lectores finalicen la lectura de los N libros en un tiempo mínimo que debe ser especificado.
Los cronogramas serán de la forma:
Hora Libro que lee Libro que lee
A B
1 ... ...
2 ... ...
... ... ...
TIEMPO EMPLEADO: ---- horas
quedando anotado en estas tablas cuál es el libro que cada lector lee en cada hora.
Los intervalos de tiempo durante los cuales A o B no están leyendo quedarán indicados poniendo 0 (cero) en el libro que lee dicha persona. Se pide además que trate de reducir el número total de intervalos de "no lectura" para ambas personas.
Sugerencia: Para el análisis del algoritmo quizás le sea conveniente considerar distintos casos:
a) K = 0 y la respuesta al punto B) sea negativa
b) K = 0 y respuesta positiva al punto B.
c) K > 2 y respuesta negativa al punto B.
d) K > 2 y respuesta positiva al punto B.
Ejemplo:
4 0
1 3
3 2
7 6
2 1
Respuesta:
El M buscado es igual a 3
Hora Libro que lee Libro que lee
A B
1 3 1
2 3 1
3 3 1
4 3 2
5 3 2
6 3 4
7 1 3
8 2 3
9 2 3
10 2 3
11 4 3
12 4 3
13 3 0
Tiempo empleado: 13 horas
Problema 68:
Un visitador médico necesita que se le arme un programa de manera de tener agendadas todas las visitas que debe hacer en un día determinado haciendo tantas visitas como sea posible para dar a los médicos la información sobre los nuevos productos del laboratorio farmacéutico que él representa.
El problema consiste en escribir un programa que permita el ingreso de los siguientes datos:
- nombre del médico
- el inicio y el final del intervalo de tiempo que el médico tiene disponible para recibir al visitador
- nombre del instituto médico donde debe realizarse la entrevista.
Hay determinadas reglas para concertar las citas que deben ser respetadas:
1- Cada visita tiene, como mínimo, 70 minutos de duración; además, el visitador necesita 30 minutos para viajar de un centro médico a otro.
2- Todos los intervalos de tiempo en los datos de entrada corresponden a un mismo día y, lógicamente, el visitador no quiere ver dos veces al mismo médico durante ese día.
3- Por reglamentación de los institutos, el visitador no puede mantener dos citas consecutivas en el mismo instituto.
4- Entre varios médicos que puedan ser visitados, el visitador siempre prefiere a aquél que pueda ser entrevistado más temprano.
5- Si hay más de un médico que pueda elegirse en un momento determinado (ya sea porque en el momento en que termina la entrevista previa ya hay médicos esperándolo o porque sus
horarios de visita comienzan más tarde pero al mismo tiempo) el visitador prefiere a aquél al cual le quede menos tiempo disponible (pero, por supuesto, el tiempo disponible debe ser, por lo menos, de 70 minutos)
6- Para visitar tantos médicos como sea posible, el visitador siempre (aún durante una entrevista) debe tener presente el momento de comienzo de la próxima entrevista de manera de poder, si fuese necesario, reducir esa cita a 70 minutos, usar los siguientes 30 minutos para viajar y comenzar la próxima entrevista de acuerdo a la regla 5.
7- Si no hay urgencia por la próxima entrevista (de acuerdo a la regla 6) el visitador permanece con el médico todo el tiempo que le permita el horario de visita.
ENTRADA:
Los horarios de visita estarán dados en la forma hh.mm y tanto los nombres de los médicos como de los institutos estarán dados sólo con letras de nuestro alfabeto.
Veamos un ejemplo:
Banegas 16.00-17.25 Pirovano
Mezzadri 09.30-11.50 Clinica
Carls 11.00-20.00 Otamendi
Dominguez 08.00-13.20 Pirovano
Novoa 22.00-23.05 Britanico
Marini 10.00-17.00 Clinica
Carls 09.20-10.40 Italiano
Estevez 19.15-20.40 Italiano
Perez 09.35-11.55 Britanico
Dominguez 18.00-20.00 Frances
SALIDA:
Deberá darse un tabla ordenada cronológicamente donde aparezcan todas las visitas propuestas. Las médicos que no puedan ser entrevistados no deberán aparecer en la tabla. En cada línea de la tabla deberá constar el inicio y fin de la cita, el lugar de la misma y el nombre del médico visitado. Si bien no debe ser exactamente igual el formato, la tabla de salida debe parecerse a la que presentamos más abajo para los datos del ejemplo dado anteriormente:
08.00-09.10 Pirovano Dominguez
09.40-10.50 Clinica Mezzadri
11.20-12.30 Otamendi Carls
13.00-15.30 Clinica Marini
16.00-17.25 Pirovano Banegas
19.15-20.40 Italiano Estevez
Problema 69:
Los distintos pisos de un edificio están numerados secuencialmente con los enteros 0, 1, 2, ..., N (N < 15). Hay K ascensores en el edificio (1 < K < 4) también numerados. El control de los ascensores está centralizado y admite dos tipos de requerimientos: internos y externos. Los externos son entrados mediante la presión de los botones que se encuentran en cada uno de los pisos y señalan si la persona que lo oprime quiere ir hacia arriba o hacia abajo. En cada piso hay dos de estos botones pues son comunes a todos los ascensores salvo en el piso 0 y en el N en los que sólo se necesita un botón. Los internos son entrados dentro de cada uno de los ascensores y consiste en pulsar el botón correspondiente a un piso dado. Debe Ud. escribir un programa que modele el control de los ascensores del edificio teniendo en cuenta las siguientes condiciones:
1- Hay un solo ascensor en el edificio (K = 1), y sólo puede aceptar un requerimiento por vez. Cualquier otro requerimiento es aceptado después de haber cumplido con el primero.
2- Hay varios ascensores en el edificio ( K > 1); cada uno de ellos acepta (e inmediatamente ejecuta) requerimientos internos sólo cuando no está ejecutando otro requerimiento. El dispositivo de control central de los ascensores puede registrar muchas entradas (producidas en los distintos pisos) al mismo tiempo, para satisfacerlas, elige uno de los ascensores que se encuentran libres o bien espera a que uno de los ascensores lo esté.
3- Considere el mismo caso que en 2), con la restricción siguiente: todos los ascensores paran en el piso 0 pero los ascensores con número par sólo paran en los pisos pares y los ascensores con número impar sólo paran en los pisos impares.
4- Considere el mismo caso que en 3), y suponga que puede haber varios requerimientos internos pendientes para cada ascensor, no sólo uno. Todos los requerimientos internos son aceptados y registrados, no importando si elascensor está o no libre.
Instrucciones adicionales: Se puede aceptar que los ascensores están sincronizados y que al iniciarse el programa se encuentran en un piso dado. Los movimientos se producen por intervalos iguales de tiempo separados por una pausa. Durante cada uno de esos intervalos, un ascensor puede ir un piso arriba o un piso abajo o permanecer en el mismo piso. Los requerimientos pueden ser entrados en cualquier pausa y son del siguiente tipo:
a) externos: <número de piso, dirección del movimiento (arriba o abajo)>
b) internos: <número de ascensor, número de piso>
En cada pausa el programa debe mostrar en qué piso se encuentra cada ascensor.
El programa debe controlar el comportamiento de los ascensores de manera que éste sea lo más inteligente posible.
Debe hacerse una clara exposición de la estrategia usada para controlar los ascensores.
Problema 70:
Consideremos mensajes escritos usando sólamente la letras mayúsculas A - Z que figuran en el teclado y los 8 símbolos: . , + - : / ? |.
Estos mensajes son enviados a través de un canal de comunicación como una secuencia de bytes. El número de unos en cada byte debe ser par.
1- Proponga un codificación de los caracteres mencionados más arriba mediante secuencias binarias de manera que no haya ambigüedad en la descodificación del mensaje y que se envíen por el canal la menor cantidad posible de bits.
2- Escriba un programa que:
2.1 Dado el texto de un mensaje, emita su codificación lista para ser enviada como una secuencia de dígitos hexadecimales.
2.2 Dado un mensaje codificado, lo decodifique y emita en pantalla el texto original.