Olimpiadas de Informatica - Problemas 21-30

Pulse aquí para volver a la página inicial

Problema 21

Cada vez con más frecuencia se usan computadoras para resolver problemas geométricos que modelizan problemas de circuitos integrados, construcción de edificios, diseño de automóviles y muchos otros. Para resolverlos es necesario tener presentes ciertas nociones de geometría como, por ejemplo:

- la ecuación de la recta que une dos puntos dados

- la definición de distancia entre dos puntos

- el sistema de ecuaciones para determinar la intersección de dos rectas.

Planteamos a continuación un problema de este tipo:

Dados n puntos en el plano coordenado de la forma (X[i],Y[i]), 1 < i < N, escribir un programa que permita:

1.- Ingresar y validar N.

2.- Ingresar las coordenadas (X[i],Y[i]) (1 < i < N) para los N puntos.

3.- Determinar si existen tres de los puntos dados que sean colineales.

Problema 22

Llamamos expresión algebraica a una función de dos variables "X" e "Y" que tiene como operadores a la suma "+" y al producto "." y como delimitadores a los paréntesis "(" y ")". Ejemplos de expresiones admitidas:

X.Y+(X+X.(X+Y).Y)

X.X.X.X+Y.Y.X+X.Y

1.- Escribir un programa "VAL.***" que permita el ingreso de:

-una expresión algebraica

-valores para X e Y

Deberá entonces evaluar la expresión para dichos valores.

Ejemplos:

- Si la expresión es:

X+X.Y.X+Y.Y+Y

en X = 1 e Y = 2 la evaluación resultará 9.

- Si la expresión es:

(Y+(X+Y.X)).X+X+Y.Y

en X = 3 e Y = 5 la evaluación resultará 97.

2.- Escribir un programa "EQU.***" que permita el ingreso de dos expresiones algebraicas y determine si son o no equivalentes. Decimos que dos expresiones algebraicas son equivalentes si y sólo si coinciden sus evaluaciones para todos los valores de X e Y.

Ejemplos:

- Las expresiones

(X+Y).(X+Y) y

X.X+X.Y)+X.Y+Y.Y

son equivalentes.

- Las expresiones

X.Y+X y

X+Y

no son equivalentes.

Restricciones técnicas.

Ambos programas aceptarán datos de entrada de archivos ASCII. VAL.*** leerá los datos del archivo VAL.DAT y EQU.*** del archivo EQU.DAT.

VAL.DAT

En cada registro del archivo se encontrará una expresión algebraica y dos números, el primero para X y el segundo para Y separados por un barra "\":

Ejemplo

X+X.Y.X+Y.Y+Y\1\2

(Y+(X+Y.X)).X+X+Y.Y\3\5

X+Y\10\11

EQU.DAT

En cada registro del archivo se encontrarán dos expresiones algebraicas separadas por una barra "\":

Ejemplo

(X+Y).(X+Y)\(X.X+X.Y)+X.Y+Y.Y

X.Y+X\X+Y

X.(X+Y)\X.X+Y.X

Cada programa deberá mostrar la solución para cada registro en pantalla permitiendo que el operador decida cuándo continuar con el siguiente registro. Deberá además grabar un registro de salida por cada registro de entrada en dos archivos ASCII correspondientes a cada programa de nombres:

VAL.SOL

EQU.SOL

Para los ejemplos de archivos de entrada mostrados más arriba, los archivos de salida serían:

VAL.SOL

EQU.SOL

Problema 23 (Torres de Hanoi)

Se tienen 3 estacas numeradas 1, 2 y 3. Supongamos que en la estaca 1 están apilados de mayor a menor n discos de distinto tamaño. Hacer un programa que indique la manera de pasar los discos a la estaca 3, teniendo en cuenta que luego de cualquier movimiento, los discos deben quedar apilados en alguna de las tres estacas y ningún disco puede quedar encima de otro de menor tamaño.

Comentario: El "rompecabezas" conocido como la Torre de Hanoi fue presentado por el matemático francés Edouard Lucas en 1883. Según el libro "Concrete Mathematics" de R. Graham, D. Knuth y O. Patashnik, Lucas introdujo el problema románticamente contando la siguiente leyenda: En el principio de los tiempos, en lo alto de la Torre de Brahma, se encontraban tres finas agujas de diamante con 64 discos de oro puro descansando en la primera de ellas. Entonces, Dios encargó a un grupo de monjes que transfirieran los 64 discos a la tercer aguja de acuerdo a las reglas que hemos dado en el enunciado del problema. Los monjes trabajan desde entonces día y noche sin descanso para completar su tarea; cuando ello ocurra, la Torre se derrumbará y el mundo habrá terminado.

Problema 24

Considerar el problema de la Torre de Hanoi cuando se tienen n discos y k estacas (k número natural y k > 4) numeradas 1, 2, ..., k para pasar los discos de la estaca 1 a la estaca k reduciendo la cantidad de movimientos hechos en el caso en que k = 3 en el problema anterior. Estimar esta cantidad para k = 3 y para k > 4 cualquiera.

Problema 25

Se tiene una lista de estaciones de ferrocarril. A efectos de simplificar, los nombres de las estaciones han sido reemplazados por 1, 2, ..., n-1, n donde n es el número total de estaciones. Se tiene , además, una lista de los tramos de vía que unen, directamente entre sí, estaciones contiguas. Los tramos de vía pueden utilizarse en ambos sentidos.

Por ejemplo, si n = 9 y los tramos son (8,1), (3,6), (4,9), (1,7), (2,7), (1,4), (5,4) y (1,9) esto podría representarse gráficamente como:

--- 9 ---

5 -------- 4 -------- 1 -------- 8

------ 7 ----- 2

6 -------- 3

a) Escribir un programa que lea n y la lista de tramos. Luego, agrupar las estaciones en líneas, donde una línea se define como un conjunto de estaciones alcanzables entre sí, y listarlas. En el ejemplo dado, se produciría un resultado semejante al siguiente:

Línea 1:

1 2 4 5 7 8 9

Línea 2:

3 6

b) Extender la solución al problema a) para determinar, para cada línea, la distancia, medida en estaciones, entre las estaciones más distantes, tomando en cada caso el camino más corto. En el ejemplo dado, se produciría un resultado semejante al siguiente:

Línea 1:

1 2 4 5 7 8 9

Distancia Máxima: 4

Línea 2:

3 6

Distancia Máxima: 1

Problema 26

Las ciudades M1, M2, ..., Mn están situadas sobre una ruta recta. No hay más que p ómnibus entre ciudades vecinas. Cada ruta está caracterizada por el horario de arribo y de llegada de cada ómnibus. Cuándo debe una persona partir de la ciudad M1 si quiere llegar a la ciudad Mn a una hora determinada? En cada cambio de ómnibus en una ciudad intermedia el pasajero pierde 1 minuto. El tiempo está dado en horas y minutos.

Determine una estructura de datos para representar los datos de entrada así como los resultados y escriba un programa que resuelva el problema.

Problema 27

Sean N objetos a1, a2, ..., aN (3 < N < 20), todos de distinto peso. Supongamos que mediante mediciones se han establecido ciertas relaciones de peso entre estos N objetos. Para i y j números naturales entre 1 y N, con el par (i,j) se indicará que el objeto ai es más liviano que el objeto aj. Por ejemplo, si N = 6, los pares (5,1), (5,3), (1,4), (4,6) indican:

- el objeto a5 es más liviano que el a1 y el a3

- a1 es más liviano que a4

- a4 es más liviano que a6

Escribir un programa que:

A- Cargue el entero N y las relaciones dadas y llame a subrutinas que resuelvan los problemas enunciados en B, C y D y muestre los resultados correspondientes.

B- Encuentre un orden para los N objetos tal que cada objeto preceda a todos los más pesados según las relaciones cargadas. Una posible ordenación seria 5, 1, 2, 4, 3, 6.

C- Determine qué mediciones adicionales (la menor cantidad posible) son necesarias para ordenar todos los objetos en forma creciente según su peso.

Problema 28

En el problema de los números telefónicos vimos cómo se podían codificar los nombres de personas para llamarlas por teléfono. Pero hay otra razón muy importante para codificar secuencias de caracteres: mantenerlas en secreto. La criptología es el estudio de sistemas para comunicaciones secretas. Desde tiempos remotos las actividades bélicas o diplomáticas han recurrido a la escritura cifrada o secreta de mensajes. En la actualidad, muchas compañías comerciales "cifran" o codifican sus bases de datos. Entre los métodos más antiguos se encuentra el empleado por César: Si una letra del mensaje ocupa el n-ésimo lugar del alfabeto, reemplácela por la que ocupa el (n+k)-ésimo lugar donde k es un número entero prefijado.

Con este método el mensaje:

ME ENCANTAN LAS MANZANAS

se transformaría para k = 3 en el siguiente mensaje cifrado:

PHHQFDQWDQODVPDQCDQDV

Este sistema es fácilmente violable pues el criptoanalista sólo tiene que determinar k entre 26 valores posibles (pues nos salteamos la Ñ) Un método mucho mejor consiste en definir una tabla de manera de saber qué sustitución debe ser hecha. Si la tabla fuese:

A  B  C   D  E  F   G  H  I   J  K   L  M  N   O  P  Q   R  S  T   U  V   W  X  Y   Z  
R  I  S   Q  P  A   N  O  W   X  U   M  D  H   Z  T  F   G  B  L   E  Y   K  C  J   V

el importante mensaje anterior tendría el siguiente cifrado:

DPPHSRHLRHMRBDRHVRHRB

Escribir un programa que permita el ingreso de una tabla de este tipo, chequeando que no se repiten las letras y que:

-Permita el ingreso de un mensaje cualquiera, emitiendo el mensaje cifrado.

-Permita el ingreso de un mensaje cifrado, emitiendo la traducción correspondiente.

Problema 29

Las paradas de ómnibus en una ciudad determinada son notadas con los números 1, 2, 3, ...., n. Sean:

M1 = (P11, ..., P1m1)

M2 = (P21, ..., P1m2)

..................................

Mr = (Pr1, ..., P1mr)

los trayectos de los r ómnibus de la ciudad, donde Pij es un número natural entre 1 y n e indica que Pij es la j-ésima parada del ómnibus i.

Si bien cada ómnibus recorre su ruta en ambas direcciones, Mi es la sucesión de paradas en sólo una dirección.

Diseñar un programa que realice lo siguiente:

A- Cargue los números n y r y las rutas M1, M2, ..., Mr.

B- Chequee cuándo se puede ir, en ómnibus, de una parada cualquiera a otra y exhiba un mensaje apropiado.

C- Cargue dos paradas numeradas i y j y muestre todos los trayectos posibles para ir de la parada i a la parada j.

D- Dadas las paradas i y j, encuentre la manera más rápida de ir en ómnibus de la parada i a la parada j sabiendo que el tiempo de viaje entre dos paradas es aproximadamente el mismo y tres veces menor que el tiempo que insume un cambio de ómnibus.

Problema 30

El método de cifrado de mensajes que vimos en el Problema 28 es más seguro que el método de César pues, en principio, un criptoanalista debería tratar con 26! tablas distintas para descifrar el mensaje. Sin embargo, este método es fácil de "quebrar" pues hay una cierta frecuencia para la repetición de cada letra en un lenguaje determinado; además, hay algunas combinaciones de letras que, en castellano, no se presentan jamás como, por ejemplo: QW, QS, JT, MX, etc. lo que hace que se descarten muchas de las tablas posibles.

Una forma de hacer este método más seguro es trabajar con una tabla y una "llave" para el mensaje. Como ya vimos, una tabla consiste en asignar a cada letra del abecedario otra letra sin repeticiones Por ejemplo:

A  B   C  D  E   F  G  H   I  J   K  L  M   N  O  P   Q  R  S   T  U   V  W  X   Y  Z  
R  I   S  Q  P   A  N  O   W  X   U  M  D   H  Z  T   F  G  B   L  E   Y  K  C   J  V

De esta manera: a la "A" se le asigna la "R", a la "B" se le asigna la "I" y así sucesivamente. Una "llave" es una sucesión de números enteros, mayores o iguales que 0, que se utiliza para sumar a cada letra del mensaje. Tomemos como llave la secuencia "1 2 3" y como mensaje la frase "SALGO DE PASEO":

llave             1    2   3    1   2    3   1    2   3    1    2   3   
mensaje           S    A   L    G   O    D   E    P   A    S    E   O

Para saber qué letra le corresponde a la primera "A" del mensaje (lugar 1 de la tabla) miramos la letra que le corresponde en la tabla a la "C" (lugar 1+2) pues a esta "A" le ha correspondido el número 2 de la llave; sin embargo, para la segunda "A" miramos en la tabla qué letra le corresponde a la "D" (lugar 1+3). Obtendremos entonces:

mensaje cifrado   L    S   Z    O   F    N   A    G   Q    L    N   G

Si cambiamos la llave por : "0 15 30 2 5", resultará como mensaje cifrado el siguiente:

Como a la letra L (lugar 12) le corresponde el lugar 12+30 y la tabla sólo tiene 26 lugares deberemos recomenzar desde la A hasta contar 42 lugares.

Escribir un programa que permita el ingreso de:

A. Una tabla del tipo descripto, chequeando que no se repiten las letras

B. Una "llave"

Luego, dé al usuario la opción de elegir entre:

1. Ingresar un mensaje para codificar

2. Ingresar un mensaje para decodificar

En ambos casos se deberá emitir en pantalla el resultado del proceso y luego permitir al usuario elija nuevamente una de las dos opciones.

Para la tabla definida damos dos ejemplos más para que puedan verificar el correcto funcionamiento del programa:

llave         1   0   7   9   1   0   7   9   1   0   7   9   1   0    
mensaje       S   U   N   O   M   B   R   E   E   S   J   O   S   E    
mensaje       L   E   E   C   H   I   J   H   A   B   F   C   L   P    
cifrado

llave          7   8   9   4   5   6   1   7   8   9   4   5   6  
mensaje        Z   A   P   A   T   O   S   A   Z   U   L   E   S  
mensaje        N   W   J   P   J   E   L   O   O   Q   T   X   J  
cifrado

Comentario: El cifrado que hemos descripto se conoce como cifrado de Vigenere. Cuando se usa una tabla para cada letra del mensaje y una llave tan larga como el mensaje en sí, se obtiene uno de los cifrados más seguros conocidos, el cifrado de Vernam, que es usado en las comunicaciones secretas de muchos países.