Problema 41:

Según nos han contado, el héroe millonario de una famosa novela soviética, el Sr. Coreiko, debía trasladar, periódicamente, una maleta conteniendo su millón de una caja de equipaje a otra. Estas cajas tenían cerraduras de N posiciones con las letras del alfabeto en cada posición. Seguramente, en cada traslado, se le presentaba al Sr. Coreiko el problema de encontrar una combinación de letras diferente de las que había utilizado con anterioridad y memorizarla ya que no podía permitirse el tomar notas. Para preservar su memoria y su imaginación, el Sr. Coreiko decidió usar cada vez una permutación distinta de una palabra de N letras (la palabra en cuestión era el nombre de la chica de la cual había estado enamorado en sus años juveniles). Todo iba bien, pero ... una vez el Sr. Coreiko olvidó la clave que había utilizado para cerrar la caja. Es necesario elaborar un algoritmo (y el correspondiente programa) de manera de dar al Sr. Coreiko la posibilidad de encontrar claves con las que deberá tratar de abrir la caja (por supuesto, el Sr. Coreiko no había olvidado el nombre de su amada). Es necesario hacer notar que, debido al tipo de educación que había recibido, al Sr. Coreiko le gustaban mucho las descripciones recursivas.

Problema 42 (II IOI, Minsk 1990):

En cierta galería de arte, los guardianes de seguridad cumplen horarios de trabajo continuo. El turno del i-ésimo guardián se anota como un par ordenado de la forma [T1(i),T2(i)] indicando T1(i) el inicio y T2(i) el fin de su jornada. El conjunto de pares ordenados de todos los guardianes define el cronograma de turnos (turnos de guardias). Escribir un programa que, dado un cronograma de turnos, permita: A) Verificar si hay o no, por lo menos, dos guardianes en la galería mientras está abierta, esto es, en cada instante del intervalo [0,FIN]. Si la condición expuesta en A) no se cumple: B) Determine todos los intervalos de tiempo durante los cuales la guardia es insuficiente, es decir, que hay menos de dos guardianes. C) Encontrar la mínima cantidad de guardianes adicionales que se requiere para que se cumpla la condición A), dada la duración de la jornada fija e igual para todos ellos. D) Indicar si es posible cumplir la condición A) sin agregar guardianes adicionales, cambiando todos los horarios de comienzo de jornada que sean necesarios pero manteniendo la duración de cada uno de ellos. E) En caso de ser afirmativa la respuesta al punto D), encontrar una solución que requiera el menor número de cambios de horario.

Entrada:

Todos los tiempos se indican en números enteros. Ingresar y validar: FIN El tiempo que debe ser cuidada la galería, es decir, la galería debe ser cuidada durante el intervalo [0,FIN]. N La cantidad de guardianes. T1(i), T2(i) para 1<i<N Los horarios de comienzo y terminación de la jornada de trabajo del guardián i. L La duración de la jornada de los guardianes adicionales.

Salida:

1- La respuesta a la pregunta A en la forma SI/NO. 2- Si la respuesta anterior es NO, la lista de pares (k, j) indicando el comienzo y el fin de todos los intervalos de tiempo con insuficiente cantidad de guardianes y el número de guardianes en cada uno de ellos (0 ó 1). 3- La cantidad de guardianes adicionales necesaria y la lista de horarios de comienzo y terminación de la jornada de cada uno de ellos. 4- La respuesta del punto D en la forma SI/NO. Si la respuesta es afirmativa, indicar el nuevo cronograma de turnos. 5- En respuesta para el punto E , el mínimo número de guardianes cuyos horarios debieran cambiarse indicando el guardián y el cambio realizado.

Problema 43:

Dos chicos juegan, con papel y lápiz, al siguiente juego: Se dibujan en una hoja N cuadraditos iguales uno al lado del otro y se elige un entero positivo K (0 < K < N < 40). Cada jugador, en su turno, debe elegir K cuadraditos adyacentes y tacharlos. El ganador es aquél que ha hecho el último movimiento. Se trata de escribir un programa que permita jugar a los chicos mediante el teclado de su computadora. El programa debe permitir: 1- Ingresar los enteros positivos N y K, validando el ingreso de estos datos. 2- Mostrar en pantalla una secuencia de los primeros N números naturales. 3- Avisar, mediante mensajes en pantalla, a cuál de los dos jugadores le toca jugar. 4- Permitir el ingreso de cada jugada mediante el ingreso del índice del primer casillero que debe ser tachado. 5- Verificar que, si el jugador introduce el número L, los casilleros con índices L, L+1, ..., L+K-1 se encuentran libres, es decir, no han sido tachados aún. 6- Si de acuerdo al punto 5) la jugada es inválida debe emitirse el mensaje correspondiente y permitir que ese jugador introduzca una nueva jugada. 7- Si la jugada es correcta, deben aparecer en pantalla asteriscos (*) debajo de los números que identifican a todos los casilleros tachados en esa jugada y a los que han sido tachados en jugadas anteriores. 1 2 3 4 . . . N * * 8- Determinar luego de cada jugada si el jugador tiene una "estrategia ganadora" entendiendo por ésta que va a ganar aún cuando el otro jugador haga las mejores jugadas posibles, emitiendo mensajes "No tiene estrategia ganadora" o bien "Tiene estrategia ganadora". 9- Cuando el juego ha terminado (es decir, cuando no quedan K casilleros consecutivos que puedan ser tachados), emitir un mensaje que especifique quién es el ganador.

Problema 44:

Dada una tabla de 4x4 cuyas celdas, excepto dos, contienen los números de 1 a 14, sin repetición y las dos restantes están en blanco como en el ejemplo de la figura 1: TABLA A TABLA B 7 3 5 14 1 2 3 4 4 9 13 5 6 7 8 1 2 10 9 10 11 12 11 8 12 6 13 14 Figura 1 Figura 2 programar la transformación de la configuración de la tabla dada en la que aparece en la TABLA B de la Figura 2. El programa debe aceptar y validar la entrada desde el teclado de los números del 1 al 14 en cualquier orden y dos ceros indicando los lugares vacíos. La entrada debe hacerse línea a línea como en el ejemplo de la figura 1. Se debe respetar la siguiente regla de intercambio: Cualquier número puede ser movido vertical u horizontalmente, pero no en diagonal, a una posición vacía adyacente. La posición previamente ocupada por ese número queda vacía. Objetivos del programa: 1.- Ingresar y validar los datos. 2.- Producir la transformación de la tabla inicial en la final, como en la figura 2. 3.- Producir la siguiente salida: Para cada movida, mostrar en pantalla: A) el número secuencial (1, 2, 3, ....) de movida. De este modo, el número total de movidas quedará indicado al final del proceso. B) a la izquierda de la pantalla, la tabla como estaba antes de la movida, y C) a la derecha de la pantalla, la tabla como queda después de la movida.

Problema 45:

Sin pensarlo demasiado, nos entrometemos en el mundo de los conejos y planteamos el siguiente ejercicio: Supongamos que una pareja adulta de conejos produce una nueva pareja de conejos cada mes y que cada pareja de conejitos llega a la adultez al cumplir un mes de vida. Si partimos entonces de una pareja recién nacida, al cabo de un mes tendremos una pareja adulta, 1 mes después habrá dos parejas (una adulta y una recién nacida) y así (suponiendo que los conejos no son mortales): 0 mes 1 pareja recién nacida 1 mes 1 pareja adulta 2 meses 2 parejas (1 adulta y 1 recién nacida) 3 meses 3 parejas (2 adultas y 1 recién nacida) 4 meses 5 parejas (3 adultas y 2 recién nacidas) Se trata entonces de escribir un programa que permita el ingreso de un número entero positivo N y determine cuántos pares de conejos se habrán producido a partir de una sola pareja después de N meses.

Problema 46:

Dados 3 puntos A, B y C en el plano coordenado de la forma (X[i],Y[i]), 1 < i < 3, escribir un programa que permita: 1.- Ingresar las coordenadas (X[i],Y[i]) (1 < i < < 3) para los 3 puntos. 2.- Decidir si los puntos A, B y C están o no alineados, emitiendo el correspondiente mensaje. 3.- En caso en que la respuesta a la parte 2) sea negativa, determinar si el "recorrido" A-B-C tiene o no el mismo sentido que el del movimiento de las agujas del reloj, emitiendo un mensaje adecuado.

Problema 47: (Problema de Josephus)

Este problema tiene su origen en una leyenda sobre el historiador Flavius Josephus en el primer siglo de nuestra era. Durante las guerras judeo-romanas, N personas, entre ellas Josephus y uno de sus amigos, se encontraron sitiadas en una cueva. Prefiriendo morir a caer prisioneros decidieron suicidarse pese a la opinión contraria de Josephus y su amigo; para ello, formaron un círculo asignándose números consecutivamente de 1 a N a partir de una persona determinada. Contando a partir de la persona número 1, la M-ésima persona se suicidó o fue ejecutada. Cerrando nuevamente el círculo y comenzando a contar desde la persona que seguía a la que fue ejecutada, al llegar al M-ésimo lugar se ejecutó a esa persona. El proceso debía repetirse hasta que sólo quedase una persona, quien debía suicidarse. Josephus, sabiendo desde qué lugar se comenzaría a contar, pudo determinar los lugares donde debían ubicarse él y su amigo de manera ser los dos últimos sobrevivientes y evitar así sus muertes. Por ejemplo, para N = 8 y M = 4, el orden en que morirían es: 4 - 8 - 5 - 2 - 1 - 3 - 7 - 6 y para N = 9 y M = 5, el orden es: 5 - 1 - 7 - 4 - 3 - 6 - 9 - 2 - 8 Se trata entonces de escribir un programa que: 1- permita el ingreso de dos enteros positivos N y M. 2- determine el orden en que morirán las N personas, mostrándolo en pantalla.

Problema 48:

Dados 2 segmentos "cerrados" en el plano (decimos que un segmento es "cerrado" cuando sus extremos forman parte de él) mediante las coordenadas de sus puntos extremos en la forma (X1[i],Y1[i]) y (X2[i],Y2[i]), 1 < i < 2, escribir un programa que permita: 1. Ingresar las coordenadas (X1[i],Y1[i]) y (X2[i],Y2[i]) ( 1 < i < 2 ) para los 2 segmentos. 2. Determinar si los dos segmentos se intersecan o no.

Problema 49:

N objetos de pesos P1, P2, ..., PN deben ser enviados por correo a una misma dirección. La forma más simple sería ponerlos todos en un mismo paquete; sin embargo, el correo no acepta que los paquetes tengan más de 8kg y la suma de los pesos podría ser mayor que eso. Afortunadamente, cada uno de los objetos no pesa más de 8kg. Se trata entonces de pensar un algoritmo que dé un m‚todo para armar los paquetes, tratando de optimizar su cantidad. Debe escribir un programa que: 1- permita la entrada de un entero positivo N 2- la entrada de los N pesos, verificando que 0 < Pi < 8 ( 1 < i < N) 3- exhiba en pantalla la forma en que los objetos deben ser dispuestos en los paquetes. Una vez que ha hecho el programa, considere qué cambios debería hacerle en el caso en que el correo cambie su disposición sobre el peso máximo de los paquetes de 8 a 10kg. Es conveniente que Ud. analice si el algoritmo que Ud. ha usado encuentra la mínima cantidad de paquetes en todos los casos.

Problema 50:

Dados N (N > 0) segmentos cerrados en el plano mediante las coordenadas de sus puntos extremos en la forma (X1[i],Y1[i]) y (X2[i],Y2[i]) para 1 < i < N, escribir un programa que permita: 1. Ingresar N y las coordenadas (X1[i],Y1[i]) y (X2[i],Y2[i]) ( 1 < i < N) para los N segmentos. 2. Encontrar una línea recta que corte a la mayor cantidad posible de los N segmentos. 3. Escribir una lista ordenada de los segmentos que la línea recta encontrada en (2) va intersecando, del primero que corta al último.

Volver