Capítulo 11

Ejercicios Propuestos al

estudiante

Ejercicios Propuestos al estudiante

1. Realizar el juego del “laberinto” en una matriz de 20x20.

En un fichero guardo una matriz con ceros y unos. Un 1 es una posición válida, mientras que

un 0 no me deja pasar. En el fichero también debe aparecer la posición final e inicial en forma

de coordenada.

2. Lo que se pide es graficar la siguiente estrella en modo texto, en C o C++.

o

o o

o o

o o o o o o o o

o ¡FELIZ o

o NAVIDAD! o

o 2000 o

o o

o o o

o o o o

o o

o o

Solo se pide que la letra "I" de la palabra NAVIDAD este en el centro de la pantalla.( por ejm si

trabajamos en una pantalla de 80 columnas y 25 líneas el centro será el punto 40,12 )

3. Carreras: Eres miembro de un equipo de carreras a campo traviesa, estas carreras son un poco

diferentes a las que conoces, ya que no importa quien llegue más rápido, sino quien lo haga de

manera más eficiente. La carrera se lleva a cabo en un terreno cuadriculado y en carros que

pueden avanzar solo en dirección vertical y horizontal, la cantidad de combustible que puede

llevar cada uno de los carros del equipo no le alcanza para llegar de la salida a la meta (una

unidad de combustible alcanza exactamente para avanzar un cuadro), en el terreno se

encuentran abastecimientos de combustible en los que los carros pueden recargar, cada uno

de los abastecimientos puede ser utilizado solo una vez durante la carrera sin importar la

cantidad de combustible que se obtenga de él. También un carro de tu equipo puede

proporcionarte combustible si se cruzan en algún lugar del terreno. Todos los carros de tu

11

equipo pueden tomar caminos diferentes, y no es necesario que vayan juntos en ningún

momento.

Problema:

Escribe un programa que dados los puntos en los que se encuentran los abastecimientos de

combustible, sea capaz de elaborar un itinerario que pueda hacer que alguno de los carros de

tu equipo realice el recorrido desde la salida hasta la meta utilizando el menor número de

carros del equipo ó en caso contrario determinar que no existe ninguna solución posible.

Límites

Tamaño del mapa (100 x 100) FIJO SIEMPRE.

Número de carros por equipo (16) FIJO TAMBIEN.

Número máximo de abastecedores (500).

Cantidad máxima de combustible por carro (15).

Entrada

Primer ingreso por teclado la cantidad de combustible que puede llevar cada uno de los carros

del equipo (todos los carros del equipo son siempre iguales y parten de la salida con el tanque

lleno).

Segunda entrada son las coordenadas (xs,ys) del punto de salida.

Tercera entrada son las coordenadas (xm,ym) de la meta.

Cuarta entrada es el número N de abastecedores que hay en el mapa, y en las últimas N líneas

están las coordenadas x, y de cada uno de los abastecedores.

Salida

Tu programa deberá escribir por pantalla el itinerario que utilizó tu equipo para llegar a la meta,

empleando para ello 4 números separados por un espacio utilizando la siguiente notación:

C Xa Ya A

Donde C es el número del carro,

Xa Ya son las coordenadas en las que se abasteció el carro C y

A puede tomar los siguientes valores:

0 si el carro C cargó combustible en un abastecimiento, el número del carro del que se

abasteció y 17 si llegó a la meta.

En caso de no existir solución posible deberá

escribir: NO SOLUCION.

Ejemplo

ENTRADA SALIDA 8

20 14

1 14

1 18 19 0

1 10 19 0

1 7 18 0

6

19 9

18 19

13 7

10 19

7 9

7 18

2 19 9 0

2 13 7 0

2 7 9 0

2 7 14 1

2 1 14 17

El carro uno se abastece en el abastecedor que se encuentra en 18, 19. El carro dos se abastece del carro uno en 7, 14. Carro dos llega a la meta.

4. Castillo: Neo ha ingresado de nuevo a la matriz y las máquinas han logrado encerrarlo en un complejo con forma de castillo medieval. Sin embargo esto no es suficiente para atraparlo, ya que él es capaz de modificar la matriz, con lo que puede hacer que desaparezcan paredes, logrando de esta forma, encontrar una ruta de escape que lo lleve de vuelta al mundo real para llegar a Zión.

Las máquinas sin embargo, pueden darse cuenta de cada cambio que se realice en el sistema, por lo que Neo desea derribar el menor número de paredes para que se dificulte su rastreo. Su tarea es ayudar a salvar la especie humana, escribiendo un programa que determine la menor cantidad de paredes que deben modificarse para salir del castillo.

Entrada

El castillo consta de m filas (2<=m<=50) cada una con n módulos (2<=n<=50) rectangulares

donde cada módulo puede estar rodeado de a lo más 4 paredes.

La entrada consta de una línea con los números m y n y a continuación m líneas cada una

describiendo los n módulos de esa fila.

El número que describe a cada módulo es un entero entre 0 y 15 que es el resultado de la

suma de: 1 si tiene pared en el lado oeste, 2 si tiene pared en el lado norte, 4 si tiene pared en

el lado este y 8 si tiene pared en el lado sur.

Por ejemplo el número 11 representa un módulo con paredes en los lados oeste, norte y sur.

Finalmente, una línea indicando la posición inicial en formato fila, columna, en la que se

encuentra Neo. Nótese que el castillo puede estar totalmente encerrado, o puede tener

módulos con salida directa al exterior. Para salir, Neo puede modificar cualquier pared, incluso

las que conectan directamente al exterior.

Salida

Un número entero que indica el menor número de paredes que debe modificar Neo para salir

del castillo y escapar de los agentes.

Ejemplo

Este el mapa del castillo ejemplo. La “X” marca el lugar inicial donde se encuentra Neo. Una

posible salida derriba dos paredes hacia el norte. Sin embargo esta no es la única forma de

salir derribando dos paredes.

5. Desórdenes:

Una permutación de los números del 1 al N es una secuencia de números a1, a2,... aN en la

cual aparece exactamente una vez cada uno de los números del 1 al N.

Un desorden de una permutación es una nueva permutación que se obtiene al realizar un

conjunto de intercambios de parejas de números en la primera tal que cada número sea

intercambiado a lo más una vez.

ENTRADA SALIDA 5 8 15 3 2 10 14 11 6 7 7 9 12 7 15 15 13 5 1 14 11 8 10 14 11 4 12 11 10 10 10 10 14 13 11 10 10 10 10 10 10 14

2 5

2

Comenzando con la permutación 1, 2,..., N se desea encontrar la menor cantidad de

desórdenes que se le deben aplicar sucesivamente para obtener una permutación dada.

Por ejemplo, para N=5 se desea obtener la permutación 3, 4, 1, 5, 2. Esto se logra con dos

desórdenes, primero intercambiando el 1 por el 3 y el 2 por el 5 para posteriormente

intercambiar el 2 por el 4.

Escriba un programa que encuentre:

la cantidad D de desórdenes (Subproblema A) y

los intercambios (Subproblema B) que se deben efectuar en cada uno de los primeros para

obtener una permutación dada.

Entrada:

La primera entrada contiene el valor de N (con 1 N 1000) y en la segunda línea una lista de

N enteros del 1 al N.

Salida:

Mostrar por pantalla en la primera línea el valor de D y en cada una de las siguientes D líneas

la cantidad K de intercambios seguida de K parejas de enteros indicando los números

intercambiados. Las parejas podrán estar escritas en cualquier orden, pero los desórdenes

deberán escribirse en el orden en que fueron aplicados.

Ejemplos

ENTRADA SALIDA

5

3 4 1 5 2

2

2 1 3 2 5

1 2 4

ENTRADA SALIDA

7

3 2 1 7 6 5 4

1

3 1 3 4 7 5 6

6. Calendario de un curso:

En una Universidad hay un grupo de M personas interesadas en tomar un curso, numeradas de

la 1 a la M. La Universidad está dispuesta a contratar los servicios de un profesor para que

imparta ese curso. El profesor tiene N fechas disponibles para dar clases, numeradas de la 1 a

la N.

La Universidad seleccionará algunos de las personas interesadas y algunas de las fechas

disponibles para el curso de modo que todas las personas seleccionadas puedan asistir a todas

las clases que se impartirán en las fechas seleccionadas.

Para ello la Universidad solicita a todos los interesados que le indiquen en que fechas pueden

asistir a las clases del curso.

Escribe un programa que encuentre una selección de P alumnos y Q fechas que cumplan las

condiciones exigidas y que maximicen el producto PQ.

Por ejemplo, suponga que M=3 y N=5, la persona 1 puede asistir en las fechas 1, 2, 4 y 5; la

persona 2 puede asistir en las fechas 2, 3 y 4; y la persona 3 puede asistir en las fechas 1, 3, 4

y 5. Entonces la Universidad seleccionará a las personas 1 y 3, las cuales pueden asistir en las

fechas 1, 4 y 5, el producto PQ es 6.

Entrada:

La primera entrada son los enteros M y N (1 M, N 30), y en cada una de las siguientes M

líneas N enteros 0 ó 1, un 0 indica que la persona no puede asistir a la clase correspondiente y

un 1 que si puede asistir.

Salida:

Mostrar por pantalla en la primera línea los enteros P y Q, en ese orden, en la segunda línea

las P personas que asistirán al curso y en la tercera línea las Q fechas en las que se impartirá

el curso. Estas dos últimas listas deberán estar en orden creciente.

Ejemplos

ENTRADA SALIDA

3 5

1 1 0 1 1

0 1 1 1 0

1 0 1 1 1

2 3

1 3

1 4 5

ENTRADA SALIDA

4 5

0 1 0 1 0

1 1 1 1 1

1 0 1 0 1

1 1 1 0 1

3 3

2 3 4

1 3 5

7. Curvas:

Todo el mundo prefiere carreteras con pocas curvas. Un ingeniero debe diseñar una carretera que una dos ciudades y quiere que tenga el menor número de curvas posible, sin importar la longitud de la carretera. Para facilitar el diseño, el ingeniero dibujó un mapa con los accidentes naturales por donde no puede construirse la carretera, tales como montañas y barrancos muy grandes. Cuadriculó su mapa y quiere que los tramos rectos de la carretera sean horizontales o verticales o diagonales. La carretera sólo puede ir de un cuadro a otro si tienen un lado o una esquina en común, y no puede pasar por un accidente natural. Hay una curva en la carretera en un cuadro donde termina un tramo recto e inicia otro. Cada cuadro del mapa se identifica por sus coordenadas, primero la columna y después el renglón. Las columnas están numeradas de izquierda a derecha iniciando con el 0. Los renglones están numerados de arriba hacia abajo iniciando con el 0. Problema Escribe un programa que dado un mapa con los accidentes naturales encuentre el menor número posible de curvas que puede tener una carretera que inicie en el cuadro donde se encuentra la ciudad A y termine en el cuadro donde se encuentra la ciudad B. Entrada La primera entrada son los enteros N y M, el número de columnas y renglones del mapa, donde 1 N 50, 1 M 50. En cada uno de los siguientes M renglones hay N números que pueden ser 1 ó 0, 1 si hay un accidente natural en el cuadro correspondiente y 0 si no hay ninguno. En el siguiente renglón (el penúltimo) la columna y el renglón de la ciudad A. En el último renglón la columna y el renglón del punto B.

Salida La primera salida el menor número de curvas que puede tener una carretera entre las ciudades A y B.

Ejemplo En el siguiente mapa de 5 por 7, la ciudad A está en el cuadro (1,1) y la ciudad B en el cuadro (4,6). Cada cuadro negro representa un accidente natural. El menor número de curvas posibles es 3. Una carretera con 3 curvas esta dibujada sobre el mapa, y los cuadros donde hay una curva están numerados:

ENTRADA SALIDA 5 7

0 0 0 1 0

1 0 1 0 0

0 0 1 0 0

1 1 0 0 1

0 0 0 1 0

0 0 1 1 0

0 0 0 0 0

1 1

4 6

3

NOTA: en todos los casos de prueba se puede diseñar al menos una carretera.

8. Incendio:

En una ciudad se han presentado últimamente una gran cantidad de incendios, y las autoridades

sospechan que estos han sido provocados por un conocido maleante. Pero mientras se realiza su

captura, el alcalde ha decidido organizar un sistema de bomberos.

La alcaldía ha dividido la ciudad en zonas y ha determinado para cada una de ellas, estadísticas

sobre el número de incendios presentados y ha determinado una medida del número de incendios

que se podrían prevenir si se asigna una determinada cantidad de bomberos a esa zona. Por

ejemplo, podemos decir que si a la zona 1 se asignan dos bomberos, se podrían prevenir tres

incendios, si se le asignan tres, se podrían prevenir seis, si se asignan cuatro se podrían prevenir

seis y para cada cantidad de bomberos asignada se pueden prevenir una cantidad determinada de

incendios

Es importante notar que esta relación no es lineal, es decir el hecho de asignar el doble de

bomberos, no implica que se puedan prevenir el doble de incendios. Además, debido a que no se

quiere que ninguna zona se considere discriminada, se debe asignar un mínimo de bomberos para

cada una, aunque en zonas sin construir es posible que este mínimo sea cero, es decir, que no sea

necesario asignar bomberos.

Debido a que esta alcaldía tiene algunos problemas respecto a las cuestiones de planeación, ha solicitado ayuda para determinar cómo distribuir los bomberos de tal forma que se puedan prevenir la mayor cantidad de incendios, mientras logra atrapar al criminal. Su tarea es escribir un programa que ayude a la alcaldía a cumplir su propósito.

Entrada:

La primera entrada consiste de n (2<=n<=50, el número de zonas) y m (2<=m<=500, el número de

bomberos disponible).

En la siguiente entrada vienen n números, que indican el número mínimo de bomberos necesarios

en cada zona. Enseguida aparecen n líneas, cada una de ellas conteniendo m números, cada

línea representando una zona, donde el i-ésimo número de esa línea es la cantidad de incendios

que se pueden prevenir en esa zona si se asignan i bomberos.

Salida:

La salida son dos líneas. La primera indica cual es la mayor cantidad de incendios que se pueden

prevenir en la ciudad. En la segunda vienen n números, en la que el i-ésimo número indica el

número de bomberos asignados a la i-ésima zona. En caso de que exista más de una

configuración que prevenga la mayor cantidad de incendios, cualquiera de ellas puede darse en la

salida.

Ejemplo

ENTRADA SALIDA

2 6 1 2 2 3 6 6 9 10 4 5 6 8 9 20

12 3 3

9. TENER ENE PADRES:

Unos extraños microbios descubiertos en un lago oculto debajo de la gruesa capa de hielo que

cubre el continente antártico han demostrado una extraña forma de reproducción que no se ha

encontrado en otros seres vivos.

En lugar de tener uno o dos padres como los demás seres vivos, pueden llegar a tener hasta N

padres, donde N puede ser un entero no mayor que 1000.

La información genética de cada padre viene dada en una cadena de a lo sumo 200 letras

mayúsculas.

La información genética que da lugar al neonato esta dada por una cadena formada por la

intercalación de un elemento de cada cadena de cada padre mientras estas cadenas tengan letras

disponibles. No todas las cadenas de los padres son de la misma longitud. La cadena del neonato

tendrá la longitud de la suma de las longitudes de las cadenas de todos sus padres, siendo esto

una curiosidad biológica adicional de estos microbios.

Problema

Debes escribir un programa para calcular la cadena del microbio neonato a partir de las cadenas

de sus padres.

Entrada:

La primera entrada es el siguiente formado:

línea 1: un número entero N (1 N 1.000) que indica la cantidad de padres.

líneas 2 a N+1: cada una con una cadena con Ci ( 1 Ci 200) letras mayúsculas indicando la

información genética de cada padre.

Salida:

La salida será hacia pantalla la cual estará formada por una sola línea. Esta línea debe contener la

cadena del microbio neonato.

Ejemplo

ENTRADA SALIDA

3

ABABAFGFG

CDCD

XZXZXEEF

ACXBDZACXBDZAXFEGEFFG

Nota: la información vertida en este enunciado es apócrifa.

10. PUEBLO ONDULADO Un pueblo de Ibero América, de cuyo nombre no quiero acordarme, se ha vuelto muy inseguro a causa de la delincuencia y el jefe de policía ha decidido poner P policías a patrullarla. Esta ciudad tiene una particularidad, ha nacido y se ha desarrollado a lo largo de una carretera, de modo tal que todo el patrullaje se reduce a la calle principal que tiene B-1 cuadras de largo, que visto de otra forma son B bocacalles. A cada policía se le debe asignar un conjunto de bocacalles consecutivas a cubrir durante su ronda, desde ellas podrá observar sin necesidad de recorrerlas las pocas casas que hay en cada calle transversal. Si a un policía le corresponde por ejemplo las bocacalles 1 a 7, el siguiente patrullará desde la bocacalle 8 y así siguiendo. Este problema se complica porque el terreno de la ciudad es fuertemente ondulado y el esfuerzo que realiza el policía no depende tanto de la distancia horizontal, puesto que todos caminan permanentemente durante su turno, sino de los desniveles que deba vencer. Para simplificar la tarea de asignación el jefe de policía determina la máxima y mínima altura que hay en el tramo que le corresponde a un policía y por diferencia determina un número representativo del desnivel. Considera una asignación buena de tramos a los policías aquella que minimiza el máximo desnivel que pudiera tocarle a algún policía. Tarea Debes escribir un programa que le ayude a determinar ese número para poder juzgar si la tarea que le impondrá a sus agentes es razonable. Se conoce la altura sobre el nivel del mar de cada bocacalle. Se ha utilizado una unidad de medida lo suficientemente pequeña para que estas alturas sean cantidades enteras. Tu resultado quedará expresada en la misma unidad.

Entrada: La entrada tiene el siguiente formato:

línea 1: los números B (1 B 10.000) y P (1 P 1.000) separados por un blanco.

líneas 2 a B+1: las alturas Yi (-400 Yi 8850) sobre el nivel del mar de las B bocacalles

Salida: La salida será hacia pantalla que contendrá una única línea con un único número: el peor desnivel que inevitablemente le tocará a algún policía.

Ejemplo

ENTRADA SALIDA

6 2 100 101 104 101 108 105

4

Podrás comprobar este resultado imaginando las distintas formas de asignar tramos a cada policía.

11. Rompecabezas

Se tienen N x N piezas cuadradas numeradas del mismo tamaño. Cada una viene con su número en el interior y con cada lado marcado con algún número. Un ejemplo de pieza 1 es el siguiente:

Se trata de acomodar las piezas en un arreglo de N x N de tal manera que si dos lados de dos piezas son adyacentes entonces esos lados deben estar marcados con los mismos números. Por ejemplo:

Las piezas no pueden ser giradas ni rotadas al momento de buscar una configuración. Entrada La primera entrada es el número N, donde 1 N 7. En las siguientes N líneas subsecuentes la descripción de cada pieza. En cada una de estas líneas (comenzando por la ficha 1) primero va el número que marca el lado vertical izquierdo y luego en sentido horario los que marcan los otros lados para cada una de las piezas. Salida En pantalla en N líneas, en cada línea van los números de las piezas en el orden hallado para cumplir las condiciones del problema de cada fila. Se garantiza que toda entrada de prueba tiene al menos una solución. Cualquier solución que cumpla las condiciones del problema es válida. Ejemplo

ENTRADA SALIDA

3 4 1 3 3 4 2 1 4 3 4 3 2 4 5 3 5 3 1 3 5 4 4 4 1 3 2 1 4 1 5 4 1 4 3 4 4

8 6 2 1 5 3 9 4 7

12. Ruleta: El juego de la ruleta ha sido objeto de innumerables intentos de descubrir alguna flaqueza que permitiera diseñar un método para obtener ganancias sistemáticas. Numerosos autores han escrito tratados de cómo saltar la banca. Norman Leigh escribió una obra clásica donde expone como, junto con doce compañeros, saltaron la banca de Montecarlo. La obra, magistralmente escrita, cuenta hechos “verídicos”. Pero con el auxilio de la ciencia de la computación podemos ver que esos hechos tal como los relata Leigh en su libro no pueden haber sucedido.

El método que Leigh relata en su libro es el Labouchere inverso. El apostador comienza anotando

en una libreta los números 1, 2, 3 y 4. Siempre apuesta una ficha igual a la suma de los números

de los extremos de la lista. Si gana agrega al final de la lista un número de igual valor al de su

última apuesta, que acaba de ganar. Si pierde tacha los dos números de los extremos de la lista. Si

en principio pierde las dos apuestas iniciales, la lista se acaba y en total ha perdido $10 y entonces

vuelve a comenzar anotando los números 1, 2, 3 y 4 en su libreta y reiniciando el método. Si la

apuesta llega a superar el límite de la mesa el jugador también reinicia el método anotando una

nueva lista de 1, 2, 3 y 4 en su libreta y apostando $5.

Recordamos que la ruleta europea consta de los números del 0 al 36 y que, jugando a par se gana

si se obtiene un número par distinto de cero, el que juega a impar gana si el número es impar y en

caso de salir cero ambos pierden. La apuesta máxima es de $100, recuerde que cuando se supera

esta apuesta el método se reinicia. En cada apuesta se gana o se pierde el monto apostado.

Con dos jugadores uno jugando a par y otro a impar el método se comporta así en unas bolas de ejemplo.

Se le pide que escriba un programa que calcule la ganancia o pérdida alcanzada luego de jugarse

cierta cantidad de bolas de ruleta.

Entrada: La entrada consta de un entero 0 < N <= 30000 en la primera línea indicando la cantidad de tiradas de ruleta y a continuación N líneas cada una con un número entero entre 0 y 36, representando las bolas obtenidas en cada uno de los N giros de la ruleta.

Salida:

La salida consistirá de dos enteros P y Q separados por un blanco indicando respectivamente la ganancia (o pérdida) de par e impar, proveniente de aplicar el método de Labouchere inverso a las apuestas de par e impar en la serie de bolas contenida en la entrada.

Sale 31 22 26 11 4 36 0 4

Par

Lista 1 2 3 4 2

3

2

3

5

2

3

5

7

3

5

3

5

8

3

5

8

11

5

8

5

8 13

Ganancia Acumulada 0 -5 0 +7 -2 +6 +17 +3 +16

Impar

Lista 1 2 3 4 1

2

3

4

5

2

3 4

3 3

3

1

2

3

4

2

3

1

2

3

4

2

3

Ganancia Acumulada 0 +5 -1 -7 -4 -10 -15 -20 -25

Ejemplo

ENTRADA SALIDA

8

31

22

26

11

4

36

0

4

16 -25

13. SIERPE ENROSCADA: En el mundo de la Herpetología Combinatoria pensaremos a las sierpes como ofidios compuestos por una sucesión de cubos del mismo tamaño articulados entre sí. Una sierpe de N x N cubos busca enroscarse formando un cuadrado de N cubos de lado. La sierpe para dormir adopta la posición, en el plano, que le permite tener el cubo 1, (la cabeza), lo más lejos posible del cubo N2, (la cola). Exceptuando la cabeza y la cola todos los demás cubos de la sierpe se articulan con los vecinos en dos caras opuestas (cubos tipo 0) o en dos caras adyacentes (cubos tipo 1). Lo que hace a una sierpe distinta de otra es la ubicación de los cubos de tipo cero y tipo uno en su conformación. Así la sierpe ilustrada tiene luego de la cabeza cuatro cubos seguidos de tipo 1 y luego alterna un cubo de tipo 0 otro de tipo 1 y finalmente otro de tipo 0. Un plegado corresponde a una rotación de 180 grados de la sierpe entre dos cubos vecinos. Aunque la rotación invade la tercera dimensión, al final de la misma la sierpe queda nuevamente en un plano.

Problema Debes escribir un programa que indique, a partir de la posición que adopta para dormir, entre que cubos debe plegarse para lograr su cometido de quedar enroscada formando un cuadrado. Luego de cada plegado ningún cubo de la sierpe puede quedar apoyado sobre otro. Se considerará como solución la lista pares de cubos vecinos entre los cuales que debe plegarse la sierpe para llegar a formar un cuadrado.

Entrada:

La sierpe viene descripta por pantalla que en su primera línea tiene el número entero N (3 N

5) que indica la raíz cuadrada de la longitud de la sierpe. A continuación el archivo tiene N2-2 líneas. Cada una con la descripción (un cero o un uno) del tipo de cada uno de los N2-2 cubos centrales (los que no son la cabeza ni la cola).

Salida: Mostrar por pantalla, a razón de uno por línea, los números de los pares de cubos entre los cuales se ha plegado la sierpe respecto de la posición de reposo separados entre sí por un blanco. Los plegados deben darse en el orden en que fueron sucediendo. En caso de haber más de una solución cualquiera se considerará como correcta.

Ejemplo

ENTRADA SALIDA

3

1

1

1

1

0

1

0

2 3

5 6

4 5

Nota 1: observen que 5-6 4-5 2-3 no es una solución porque después de plegar en 5-6 no puede hacerse el plegado en 4-5 debido a que se produce la superposición de los cubos 1 y 9.

Nota 2: Todas las sierpes que se presenten como casos de prueba tendrán al menos una forma de enroscarse para formar un cuadrado. Nota 3: Si hay más de una solución, basta con listar una. 14. Territorios: En el juego "territorios" dos jugadores A y B se alternan para ir destruyendo el territorio del enemigo. El terreno de juego es una cadena de N territorios alineados, 1 N 120. El territorio 1 limita sólo con el territorio 2 que limita a su vez también con el territorio 3 que limita a su vez también con el territorio 4, hasta llegar al territorio N-1 que limita con los territorios N-2 y N que a su vez sólo limita con el territorio N-1. El primero que juega es A quien es dueño de todos los territorios impares, mientras que B quien juega en segundo turno es dueño de todos los territorios pares. Cada territorio i esta inicialmente ocupado por una cantidad entera Ti de soldados, 0 Ti 500. En cada turno un jugador puede aniquilar los soldados de un territorio enemigo si la cantidad de soldados suyos en un territorio vecino o la suma de los soldados en sus dos territorios vecinos es superior a la cantidad de soldados que tiene el jugador enemigo en ese territorio, quedando 0 soldados en el territorio vencido. Si un jugador no puede jugar deberá cederle el turno al otro jugador. Cuando ninguno de los dos pueda jugar se dará por terminado el juego. El puntaje que obtiene el jugador A es igual a la cantidad de terrenos salvados por A menos los salvados por el jugador B. Si el puntaje de A es positivo gana A, si es negativo gana B y 0 significa un empate. Problema Escribe un programa que dados todos los Ti halle el valor del juego para A, considerando que ambos jugadores hacen la mejor jugada posible en cada turno, es decir utilizan una estrategia óptima. Entrada La primera entrada tiene el entero N y las siguientes N líneas tienen los enteros Ti, 1 i N.

Salida La salida se hará escribiendo el valor del juego para A en pantalla Ejemplo

ENTRADA SALIDA

5 33 71 56 44 21

2

15. Agente de Comunicaciones: En toda área de telecomunicaciones se transmiten datos de un origen a un destino, por ejemplo en el caso de AVL (Automatic Vehicle Location – Localización automática de Vehículos) la transmisión es realizada desde un origen móvil (Vehiculo) hacia un destino Centro de Control (Oficina central de una empresa donde se recibe la información) tal como se ve en el la ilustración 1.

Ilustración 1 Esquema General de un sistema AVL

Todos los mensajes son del mismo tamaño y contienen datos como tiempo, posición, velocidad y

rumbo.

Al centro de control llegan mensajes de varias unidades móviles, estos mensajes forman una cola

de mensajes el cual debe ser procesado por un Agente de comunicaciones que finalmente

muestra al usuario información útil.

Problema Implementar un Agente de Comunicaciones que tiene como entrada una cola de mensajes y

como salida un reporte con información procesada.

La cola de mensajes es una cadena de texto que contiene uno o más mensajes.

>C847B7622083466200000780>C84811082098A30C1E02D78A>C847B87520EE17C72805A79E>C942F2AE20EF08522310E796

>C943E6D220EEB2625C1187A0

Agente

De

Información

Procesada

Cola de Mensajes

recién llegados

Unidad Móvil 201

Unidad Móvil 200

Mensajes Mensajes

Centro de Control

Usuario

Un mensaje tiene un tamaño único de 26 caracteres conteniendo las siguientes partes indicadas

en Anexo 1.

>C847B7622083466200000780

El agente de comunicaciones tendrá como entrada solo la cola de mensajes.

Debe procesar los mensajes para obtener a partir de su formato hexadecimal sus respectivos

valores decimales de acuerdo al Anexo 2.

Finalmente imprimir en pantalla un reporte de acuerdo a las reglas indicadas en el Anexo3.

------------------------------------Reporte de Mensajes Procesado-------------------------------------

Total Unidades : 2

Total de Mensajes: 5

------------------------------------------------------------------------------------------------------

Unidad: 200 Total de Mensajes: 3

Orden Longitud Latitud Vel. Rumbo Tiempo Est. Operativo Est. Posición

1 75.204434 15.603655 40 090 2006/05/08 08:30 En Movimiento En Zona Normal

2 75.567234 10.003212 30 045 2006/05/08 08:10 En Movimiento En Zona Prohib

3 75.200034 08.603234 00 000 2006/05/08 08:00 Detenido En Zona Normal

------------------------------------------------------------------------------------------------------

Unidad: 201 Total de Mensajes: 2

Orden Longitud Latitud Vel. Rumbo Tiempo Est. Operativo Est. Posición

1 71.200034 15.643234 92 280 2006/05/08 08:32 Velocidad Alta En Zona Normal

2 70.200034 15.665234 35 270 2006/05/08 08:22 En Movimiento En Zona Normal

Los procesos solicitados son:

Anexos Anexo1: Estructura de cada Mensaje

Parte \ Descripción Tipo Carácter (*) Numero de Caracteres

Posición Inicial

Posición Final

Datos Adicionales

Carácter Inicial > 1 1 1 Siempre tiene valor “>”

Unidad HH 2 2 3 Código de la unidad móvil

Longitud HHHHHHH 7 4 10 Coordenada x

Latitud HHHHHHH 7 11 17 Coordenada y

Velocidad HH 2 18 19 Km./h

Rumbo HHH 3 20 22 Grados (0° a 360°)

Tiempo HHHH 4 23 26 Total de Minutos transcurridos de la semana actual.

(*) H representa un digito Hexadecimal para su conversión a decimal ver Anexo 4.

Anexo2: Ejemplo de una Cola de Mensajes que se ingresara como entrada al programa:

>C847B7622083466200000780>C84811082098A30C1E02D78A>C847B87520EE17C72805A79E>C942F2AE20EF08522310E796

>C943E6D220EEB2625C1187A0

Ordenada resultaría:

Carácter Inicial Unidad Longitud Latitud Velocidad Rumbo Tiempo > C8 47B7622 0834662 00 000 780

> C8 4811082 098A30C 1E 02D 78A

> C8 47B8752 0EE17C7 28 05A 79E

Proceso de Descodificación de los mensajes

Reporte :Listado de los mensajes procesado

Reporte :El Listado ordenarlo cronológicamente descendentemente

Reporte :Los mensajes agruparlos por unidad y poner los totales de mensaje por grupo y el total general

Reporte :Para el calculo de los estados Operativo

Reporte :Para el calculo de los estados Posición

> C9 42F2AE2 0EF0852 23 10E 796

> C9 43E6D22 0EEB262 5C 118 7A0

Procesada de hexadecimal a decimal resultaría:

Carácter Inicial Unidad Longitud Latitud Velocidad Rumbo Tiempo > 200 75200034 08603234 0 0 1920

> 200 75567234 10003212 30 45 1930

> 200 75204434 15603655 40 90 1950

> 201 70200034 15665234 35 270 1942

> 201 71200034 15643234 92 280 1952

Formateando latitud y longitud(*) y calculado la fecha hora(**) correspondiente resultaría:

Carácter Inicial Unidad Longitud Latitud Velocidad Rumbo Tiempo (Fecha Hora) > 200 75.200034 08.603234 0 0 2006/05/08 08:00

> 200 75.567234 10.003212 30 45 2006/05/08 08:10

> 200 75.204434 15.603655 40 90 2006/05/08 08:30

> 201 70.200034 15.665234 35 270 2006/05/08 08:22

> 201 71.200034 15.643234 92 280 2006/05/08 08:32

(*)Para Latitud y Longitud dividir el valor decimal entre 100000.

(**)Para el calculo de la fecha y hora agregar a la fecha hora inicial de la semana (domingo a las o horas) la

cantidad de minutos correspondiente al mensaje.

Anexo3: Reglas de negocio a cumplir para elaborar el reporte:

El Listado ordenarlo cronológicamente descendentemente

Los mensajes agruparlos por unidad y poner los totales de mensaje por grupo y el total general

Para el calculo de los estados Operativo son tres posibilidades: o Detenido.- si la velocidad es cero o En Movimiento.- si la velocidad es mayor a cero y menor a 90 km/h o Con Velocidad Alta.- si la velocidad es mayor o igual a 90 km/h

Para el calculo de los estados Posición son dos posibilidades(*): o En Zona Normal.- si no esta dentro de la zona Prohibida o En Zona Prohibida.- si esta dentro de la zona Prohibida

(*)La Zona Prohibida es un rectángulo definido mediante coordenadas de dos vértices en diagonal: (70.000000,

09.000000) (80.000000, 12.000000)

Anexo4: Un numero Hexadecimal esta compuesto por los dígitos: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E y F

Y su equivalente unitario en decimal es el siguiente:

DígitoHexacecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F

DígitoDecimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Para transformar un número hexadecimal a su correspondiente decimal debes realizar la sumatoria del

equivalente real (es equivalente unitario por potencia de 16, la potencia depende de la posición del

digito) de cada digito Por ejemplo:

2BC4 hexadecimal es equivalente a 11204 decimal pues:

4*(16^0) + 12*(16^1) + 11*(16^2) + 2*(16^3)=11204