Problema 81:
Escriba un programa que permita el ingreso de un número natural N (N<=1000) y que encuentre el número natural menor igual que N que tenga el mayor número de divisores. Si hubiese varios de tales números, el programa deberá imprimirlos todos junto con los divisores de cada uno.
Problema 82:
Escriba un programa que permita el ingreso desde el teclado de dos números romanos, los sume y dé el resultado de la suma expresado también en números romanos. Los datos de entrada se pueden suponer correctos y ni ellos ni la suma de ambos excede el número MMMCMXCIX (3999).
Problema 83:
Se considera un grupo de N personas donde cada una de ellas es amiga de más de [N/2] (parte entera de N/2) de las otras y tiene, a lo sumo, K (0 < K < N - [N/2]) enemigos en el grupo. Una de las personas tiene un libro que todos desearían leer y luego discutirlo con alguna de las personas del grupo.
Escriba un programa que:
1- Permita el ingreso desde el teclado de los enteros
N (N > 3)
K (0 < K < N - [N/2])
S (1 <= S <= N)
P (0 <= P <= K)
2- Encuentre y describa una manera de que el libro circule entre todas las personas del grupo de manera que cada persona lo reciba sólo una vez pasándolo a un amigo suyo y que, finalmente, vuelva el libro a su dueño.
3- Divida a las personas en S subgrupos, para la discusión de los temas tratados por el libro, de manera que, en cada uno de ellos, cada persona que lo integra se encuentre con, a lo sumo, P enemigos.
Se supone que S*P >= K.
Problema 84:
Dadas 2XN casilleros alineados (N > 1), de los cuales hay dos contiguos que están vacíos y en los restantes hay (N - 1) "A" y (N - 1) "B".
Por ejemplo para N = 5
A B A B A B A B
Regla de Intercambio:
El contenido de dos casilleros no vacíos adyacentes puede ser movido a las posiciones de los casilleros vacíos, preservando el orden.
Objetivo:
Obtener, luego de los movimientos que hagan falta, la siguiente configuración: todas las A estén a la izquierda de todas las B, sin importar dónde se encuentren los dos casilleros vacíos.
Escriba un programa que repita los siguientes pasos hasta que el archivo que contiene los datos de entrada, "ORDEN.DAT" sea leído totalmente:
1- Lea el próximo registro y muéstrelo en pantalla. Cada registro está compuesto por el valor de N seguido de un espacio en blanco y, a continuación, la secuencia de símbolos A, B y 0 , cero representando a los casilleros vacíos. Para el ejemplo el registro correspondiente sería:
5 ABA00BABAB
Programe la regla de intercambio.
2- Para el registro leído (estado inicial) encuentre algún método que le permita decidir si el objetivo es o no alcanzable informando, mediante mensajes en pantalla, "NO ES ALCANZABLE EL OBJETIVO" o bien "SI ES ALCANZABLE EL OBJETIVO y la forma de hacerlo es la siguiente:" mostrando a continuación el estado inicial, los estados intermedios paso por paso y el estado final. Tanto el mensaje correspondiente al caso resuelto como los estados mostrados en pantalla se grabarán también en un archivo de texto de nombre "SOL.SOL".
3- Encuentre un método que llegue al estado final en la mínima cantidad de pasos.
Ejemplos para verificar el correcto funcionamiento del programa:
E1) 3 B 0 0 A A B
NO ES ALCANZABLE EL OBJETIVO
E2) 7 A A B B B A A A B 0 0 B B A
EL OBJETIVO ES ALCANZABLE DE ESTA MANERA:
A A B B B A A A B 0 0 B B A
A A B 0 0 A A A B B B B B A
A A B B A A A A B B B B 0 0
A A 0 0 A A A A B B B B B B
E3) 6 A A A B 0 0 A B B B B A
EL OBJETIVO ES ALCANZABLE DE ESTA MANERA:
A A A B 0 0 A B B B B A
A A A B B A A B B B 0 0
A A A 0 0 A A B B B B B
Problema 85 (Mendoza, Argentina, octubre de 1993):
Se tiene un collar de n perlitas de colores (n <= 100) algunas de las cuales son rojas, otras azules y otras blancas, mezcladas arbitrariamente. Veamos dos ejemplos de collares con 29 perlitas:
1 2 1 2
o x x o x o o x
o x x x
o o x o
o o @ o
x o @ @
x x o o
x x x x
x x o x
o o x o
x o o o
x o o o
o o o x
o x o o o @
Figura a Figura b
o perlita roja
x perlita azul
@ perlita blanca
(Las perlitas que se toman como primera y segunda en el texto que sigue, han sido marcadas en el dibujo.)
La configuración de la Fig. a) puede ser representada por una cadena de caracteres b y r, donde b representa una perlita azul y r una perlita roja, de la siguiente manera:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
Supongamos que Ud. corta el collar en algún lugar y recoge las perlitas del mismo color que se desprendan hasta que encuentre una perlita de distinto color y hace lo mismo con las perlitas del otro extremo (las cuales podrían ser de diferente color de las que recogió con anterioridad).
Se trata de determinar el punto donde el collar debe ser cortado de manera de llevarse la mayor cantidad posible de perlitas.
Por ejemplo en la Fig. a), pueden ser desprendidas 8 perlitas cortando el collar entre la perlita 9 y y la perlita 10 o bien haciendo el corte entre la 24 y la 25.
En algunos collares se han incluido perlitas blancas como en la Fig. b). Cuando se hace el corte y se desprenden las perlitas, una perlita blanca encontrada puede ser tratada tanto como si fuese roja o como si fuese azul y pintada del color que se quiera que asuma. La cadena de caracteres que representará esta situación incluirá los símbolos r,b y w (donde w representa una perlita blanca).
Escriba un programa que:
1. Lea una configuración del archivo ASCII de entrada de datos, NECKLACE.DAT, con cada configuración en una línea del archivo, y la escriba en un archivo de salida ASCII, NECKLACE.SOL. Un ejemplo de un archivo de entrada podría ser:
Ejemplo:
NECKLACE.DAT
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb
2. Para cada configuración, determine el máximo número de perlitas que pueden desprenderse del collar así como un lugar donde realizar el corte.
3. Escriba en el archivo ASCII de salida, NECKLACE.SOL, la cantidad de perlitas que se recogerán y el lugar donde debe ser cortado el collar. Las soluciones a las distintas configuraciones deberán estar separadas por un registro en blanco.
Ejemplo de:
NECKLACE.SOL
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
8 entre 9 y 10
bbwbrrrwbrbrrrrrb
10 entre 10 y 17
Problema 86 (Mendoza, Argentina, octubre de 1993):
La situación económica se ha puesto muy mala. Debido a la escasez de dinero circulante y de créditos disponibles, muchas fábricas han contraído deudas que no pueden pagar. Hay, a lo sumo, 1000 fábricas.
Todas las fábricas actúan tanto como vendedoras (de los productos que fabrican) como compradoras (de los insumos que necesitan). Por lo tanto, contraen deudas entre ellas. Finalmente, ha surgido la idea de pagar deudas con ... deudas.
Supongamos que la fábrica A debe $100 a la fábrica B, la fábrica B debe $50 a la fábrica C y C debe $75 a A. La suma de todas las deudas es $225.
La fábrica A usa su crédito con la fábrica C para pagar parte de su deuda con la fábrica B. Así,
A a B $25
B a C $50
C a B $75
Entonces, la deuda total puede ser reducida a una suma mínima y la lista de deudas resulta:
A a B $25
C a B $25
El problema consiste en escribir un programa para pagar deudas con deudas.
1. Lea una lista de deudas del archivo ASCII de entrada de datos, DEBT.DAT, y escriba estos datos en el archivo ASCII de salida, DEBT.SOL,. Cada registro de la lista consiste de dos códigos de fábricas y el monto adeudado de la primera a la segunda. Las distintas listas a ser consideradas estarán separadas por un registro en blanco como se muestra en el ejemplo al final del enunciado.
Calcule la deuda total inicial y escriba el importe en DEBT.SOL.
2. Reconstruya la lista de deudas de manera que la suma total adeudada sea mínima. Escriba en DEBT.SOL, la nueva lista de deudas en la misma forma en que se escriben los datos de entrada.
3. Escriba en DEBT.SOL, el total de la deuda de la nueva lista hallada.
Ejemplo:
DEBT.DAT
A B 100.00
B C 50.00
C D 75.00
A B 1500.00
B C 700.00
D A 2800.00
B C 400.00
DEBT.SOL
A B 100.00
B C 50.00
C A 75.00
Total de deuda = $225.00
A B 25.00
C B 25.00
Total de deuda = $50.00
A B 1500.00
B C 700.00
D A 2800.00
B C 400.00
Total de deuda = $5400.00
D A 600.00
D B 1100.00
D C 1100.00
Total de la deuda = $2800.00
Problema 87 (Mendoza, Argentina, octubre de 1993):
En la ciudad de Sinistra, la Municipalidad ha prohibido girar a la derecha. Para obligar al cumplimiento de esta regla, es obligatorio instalar en todo vehículo un aparato que registra las coordenadas del vehículo cada vez que éste dobla. Al terminar un viaje, una sucesión de posiciones se transmite a una computadora municipal que calcula el total de la multa sumando $50 por cada giro a la derecha. Es problema a resolver es: dada la sucesión de posiciones de un vehículo, calcular el total de la multa.
Detalles:
Un viaje se representa como una sucesión de 2 o más puntos: p1, p2, ...., pN. Cada punto es un par de números (i, j), donde i y j son las coordenadas del punto en un sistema de coordenadas que tiene como origen al edificio de la Municipalidad.
p1 es el punto donde empezó el viaje, pN es donde terminó y los demás puntos son esquinas donde el vehículo dobló. Las calles son rectas de dirección arbitraria.
El problema consiste en escribir un programa que:
1. Lea de un archivo ASCII de entrada de datos, SINISTRA.DAT , y escriba en un archivo ASCII de salida, SINISTRA.SOL , el número N en una línea y cada punto del recorrido en las N líneas siguientes. Cada caso a analizar estará separado del siguiente por una línea en blanco como se muestra en ejemplo.
2. Calcule el total de la multa correspodiente al recorrido analizado.
3. Escriba en SINISTRA.SOL el total de la multa que debe ser pagada a la Municipalidad por cada viaje. Separe los distintos casos analizados con un registro en blanco.
Ejemplo:
SINISTRA.DAT
3
4 1
5.5 4
5 2
4
0 1
-1 0
0 -1
1 0
SINISTRA.SOL
3
4 1
5.5 4
5 2
Multa: $50
4
0 1
-1 0
0 -1
1 0
Multa: $0
Problema 88: (Final Nacional 1993, Primer Nivel)
Los datos de entrada son las longitudes de los lados de un rectángulo, dadas por números enteros positivos. Se dibuja una línea recta desde uno de los vértices formando un ángulo de 45° con los lados adyacentes. Cuando se alcanza uno de los lados del rectángulo, no se lo cruza sino que se cambia la dirección con un giro de 90° (manteniéndose dentro del rectángulo). Al alcanzar otro lado se vuelve a cambiar la dirección girando 90° otra vez y así se sigue hasta que se alcance cualquiera de los vértices del rectángulo. El dibujo así obtenido se parece a la trayectoria de una bola de billar en una mesa rectangular.
Escriba un programa que:
-permita el ingreso desde el teclado de:
a la longitud de la base del rectángulo dada por un entero positivo
b la longitud de altura del rectángulo dada por un entero positivo
c el número de orden del vértice desde el cual se comenzará el dibujo, de acuerdo a la siguiente convención:
1 vértice inferior izquierdo
2 vértice superior izquierdo
3 vértice superior derecho
4 vértice inferior derecho
-dé el número de veces en los que la línea se quebró y el largo total de la línea dibujada.
Ejemplo 1:
Ingrese la longitud de la base:
6
Ingrese la longitud de la altura:
4
Ingrese el vértice inicial para el dibujo:
2
Cantidad de puntos donde la línea se quebró = 3
Longitud de la línea dibujada = 16.97
Ejemplo 2:
Ingrese la longitud de la base:
20
Ingrese la longitud de la altura:
6
Ingrese el vértice inicial para el dibujo:
4
Cantidad de puntos donde la línea se quebró = 11
Longitud de la línea dibujada = 84.85
Problema 89: (Final Nacional 1993, Segundo Nivel)
ChefArg S.A. se dedica a la preparación de cenas empresariales que se sirven en su salón del centro de la ciudad. En este momento N empresas distintas han requerido sus servicios. Cada una de ellas ha fijado una cantidad de días a partir de hoy como plazo máximo para realizar la cena. ChefArg no puede atender a más de una empresa por noche. Debido a los menúes y vinos seleccionados y a la cantidad de invitados de cada empresa, la ganancia que cada una de estas cenas le redituará a ChefArg no es pareja. El Gerente General de ChefArg necesita dar una respuesta a cada una de las N empresas informándole si atenderá o no su pedido y, en caso afirmativo, cuándo se realizará la cena; demás está decir que pretende que la ganancia obtenida por ChefArg sea máxima.
Ud. es el programador que debe encargarse de dar una solución al Gerente General. Para ello, en un archivo de entrada ASCII, CHEF.DAT, se han escrito distintos juegos de datos. En cada uno de ellos figura:
N (el número total de empresas)
g1 d1 (la ganancia en $ y el plazo en días de la cena para la empresa 1)
g2 d2 (la ganancia en $ y el plazo en días de la cena para la empresa 2)
........
gN dN (la ganancia en $ y el plazo en días de la cena para la empresa N)
donde los números N, gi, di (1 <= i <= N) son enteros positivos.
Escriba un programa que:
1. Lea en CHEF.DAT el siguiente juego de datos.
2. Determine a cuáles de las empresas se les responderá afirmativamente y fije el día en que se realizará la cena de cada una de ellas respetando los plazos máximos fijados de forma tal que la ganancia obtenida por ChefArg sea máxima.
3. Escriba en un archivo ASCII de salida, CHEF.SOL:, en forma cronológica los días de las cenas junto con el número de la empresa atendida. Deberá agregarse también la ganancia máxima obtenida mediante este cronograma.
Las respuestas a los distintos juegos de datos deberán separarse con un registro en blanco.
Ejemplo:
CHEF.DAT
5
50 1
25 2
44 4
30 2
20 1
11
45 10
35 6
60 7
100 3
20 2
20 2
40 4
35 3
10 5
20 1
40 4
CHEF.SOL
Día 1: cena para la empresa 1
Día 2: cena para la empresa 4
Día 3: cena para la empresa 3
Total ganancia obtenida= $124
Día 1: cena para la empresa 4
Día 2: cena para la empresa 8
Día 3: cena para la empresa 7
Día 4: cena para la empresa 11
Día 5: cena para la empresa 9
Día 6: cena para la empresa 2
Día 7: cena para la empresa 3
Día 8: cena para la empresa 1
Total ganancia obtenida= $365
Problema 90:
Escriba un programa que permita el ingreso de la fecha de nacimiento de una persona (día, mes y año) y que dé la lista de los años, junto con la edad de la persona en esos años, en los que esa persona festejó su cumpleaños en el mismo día de la semana en que nació. Complete, además, la lista para los años subsiguientes hasta que esa persona cumpla 100 años.