Olimpiadas de Informatica - Problemas 71-80

Pulse aquí para volver a la página inicial

Problema 71: Continentes misteriosos (Bonn, Alemania, julio de 1992)

Un MAPA es un rectángulo de COORDENADAS de 48 por 16. Dos coordenadas se dicen CONECTADAS si son vecinas en la dirección sur-norte o en la este-oeste. Al principio, cada coordenada está marcada como:

A - de agua

T - de tierra

Sin embargo, hay 4 tipos posibles de Coordenadas de Tierra (CT)

T , M , P y C

y 4 tipos posibles de Coordenadas de Agua (CA):

A , O , B y L

Se debe asumir que fuera del MAPA está el Océano (O).

Hay ciertas "reglas geográficas" para cambiar (reclasificar) el tipo de una coordenada. Una coordenada debe cambiarse a:

- MONTAÑA (M): Si es una CT y está conectada con 4 CT.

- PENINSULA (P): Si es una CT y está conectada a:

- 3 CA

- o a 2 CA y, al menos, a 1 P

- o a 1 CA y, al menos, a 2 P.

- COSTA (C): Si es una CT y no es ni M ni P

- OCEANO (O): Si es una CA y está conectada a, al menos, una O.

- BAHIA (B): Si es una O y está conectada a:

- al menos, a 2 B y, a lo sumo, a 1 O

- o a 1 B y, al menos, a 2 CT

- o, al menos, a 2 CT y, al menos, a 1 O

- LAGO (L): Si es una A y ha permanecido sin cambios en su tipo luego de

haberse hecho todos los cambios posibles en las otras coordenadas.

Puede suceder que una coordenada cuyo tipo ya ha sido cambiado, deba ser clasificada nuevamente debido a que se ha modificado el tipo de algunas de sus coordenadas vecinas.

Un MAPA se dice EXPLORADO cuando no es posible ninguna reclasificación.

Problema:

Escriba un programa que repita los pasos siguientes, hasta que un archivo de entrada dado, conteniendo varios mapas, haya sido totalmente leído:

1.- Lea el siguiente mapa de un archivo de entrada ASCII (para la estructura de los datos en ese archivo, mire el ejemplo que figura al final) mostrándolo en pantalla junto con la cantidad

de coordenadas A y T que hay marcadas.

El nombre para el archivo ASCII de entrada del cual se lee la

información es: "MAPAS.MAP"

2.- Reclasifique las coordenadas correctamente con M, P, C, O, B o L respetando las reglas geográficas dadas, hasta que el mapa quede totalmente explorado.

3.- Muestre el mapa explorado en pantalla dando la cantidad de los diferentes tipos de coordenadas encontradas en una estadística final (vea el ejemplo).

4.- Escriba el mapa explorado en un archivo de salida ASCII rotulado:

SOL.SOL

EJEMPLO:

Mostramos un mapa tal como deberá verse en pantalla incluyendo el resultado del conteo que hará su programa:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAATTTTTTAAAAAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAATTAATTAAAAAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAATTTATTAAAAAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAATTAATTAAATTTATAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAATTTTTTTTTTTTTAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAATTTAAATTAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAATTTTAATTAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAAATTAAATTAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAAAATAAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAAATTTAAAAAAAAAAAAAAAAAAAAAAA

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

ESTADISTICA INICIAL: T=61 A=707 TOTAL=768

El mapa explorado correspondiente junto con la estadística final es:

OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOccccccOOOOOOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOccLLccOOOOOOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOcMPLccOOOOOOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOccLLccBBBcccBPOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOBccccccccMccccBOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOBcMcBBBccOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOOcMcBOOccOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOOcMMPOOccOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOOBccBOOccOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOOOPPPOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

ESTADISTICA FINAL: P=8 C=47 M=6 O=685 B=17 L=5 TOTAL=768

NOTA: - Hemos usado la letra "c" minúscula en lugar de la mayúscula para que sea más clara la impresión del ejemplo.

- Recuerde que la ejecución satisfactoria de su programa en este ejemplo no garantiza que su programa sea correcto!!!!

Problema 72:

Se da un icosaedro (poliedro regular de 20 caras) con sus caras numeradas de 1 a 20. El icosaedro puede ser rotado de manera que cada una de sus caras se alcance sólo una vez. La ruta elegida para recorrer todas las caras tiene un costo C definido por:

C = 1*f1 + 2*f2 + ... + i*fi + ... + 20*f20

donde fi es el número correspondiente al lado alcanzado en el paso i-ésimo.

Se puede pasar de una cara a otra sólo si estas dos caras son adyacentes teniendo en cuenta que:

Decimos que dos caras son adyacentes sólo en estos casos:

A.- Si tienen una arista en común

B.- Si tienen una arista o un vértice en común.

Se trata de escribir un programa que encuentre las rutas con mínimo costo primero para el caso A y luego para el caso B.

Nota: Si por la cantidad de tiempo o espacio empleado por el programa no puede Ud. hallar la solución exacta, proponga una solución satisfactoria.

Problema 73:

Una empresa se dedica a la construcción de puentes colgantes que quedan suspendidos mediante gruesos cables. Estos cables se fijan a torres muy altas construidas con ese propósito. Esta empresa, para garantizar las normas de seguridad en sus puentes, necesita conocer la longitud del cable de suspensión de cada puente en distintos momentos (pues el cable puede ceder más de lo aconsejable). Esta medición debe hacerse con un error menor que un número positivo R fijado. Puesto que la medición directa no puede ser exacta ya que el cable se encuentra muy alto y es curvo, se les hace necesario poder calcular su longitud conociendo sólo los siguientes datos:

L: la distancia entre los puntos de las dos torres donde se sujeta el cable.

H: la altura de esos dos puntos al suelo.

h: la distancia entre el punto más bajo del cable y la recta horizontal que une las bases de las torres.

Lo más importante es que los ingenieros saben que la curva descripta por el cable es un arco de parábola. Se hace necesario entonces escribir un programa que:

A- permita la entrada desde el teclado de los números R, L, H y R verificando que son coherentes con el problema.

B- informe la longitud del cable con un error menor que R.

Problema 74: (Atenas, Grecia, mayo de 1991)

Enumerar todas las posiciones de una matriz 5x5 de la siguiente manera:

Si el número i (1 < i < 24) es asignado a la posición (x,y) de la matriz entonces el siguiente, i+1, puede ser asignado a la posición (z,w) siempre y cuando cumpla alguna de estas tres condiciones:

1) (z,w) = (x + 3, y)

2) (z,w) = (x, y + 3,)

3) (z,w) = (x + 2, y + 2)

El problema es:

A) Escribir un programa que enumere las posiciones de una matriz 5x5 para una posición inicial con el número 1.

B) Calcular el número de todas las posibles enumeraciones tomando como posición inicial cada una de las posiciones de la matriz diagonal superior incluyendo la diagonal.

Ejemplo: Si se elige la posición (2,2) como inicial asignándole el número 1 entonces

el número 2 puede ser asignado a una de las siguientes posiciones: (2,5), (5,2) o (4,4). Estas posiciones están marcadas con un asterisco (*) en la figura:

                      
     1             *  
              *       
     *

Nota: Se tendrá en cuenta si la presentación de salida en pantalla es como la de la figura.

Evalución:

(A): 50 puntos

(B): 25 puntos

Presentación de salida en pantalla: 15 puntos

Jurado: 10 puntos (claridad, estilo, elegancia)

Problema 75: (Atenas, Grecia, mayo de 1991)

Un S-término es una secuencia de letras "S" y paréntesis definido recursivamente de la siguiente manera:

La letra S es un S-término.

Si M y N son S-términos entonces (MN) es también un S-término.

Ejemplo de S-término:

((((SS)(SS))S)(SS))

Los paréntesis a derecha no proveen información adicional, por lo tanto, pueden ser omitidos; por ejemplo, (MN en lugar de (MN), es así que el S-término del ejemplo anterior puede ser reescrito de la forma:

((((SS(SSS(SS

La longitud de un S-término es la cantidad de caracteres "S" que contiene.

1.- Escriba un procedimiento "GENSTERM" para generar S-términos: su procedimiento deberá generar n archivos de texto conteniendo todos los S-términos de longitud 1 ,..., n respectivamente. Dos S-términos consecutivos deberán estar separados por un punto y coma ";". Al final del último S-término de cada archivo deberá haber un punto ".".

Escriba un programa que permita el ingreso de un entero positivo n (n < 10), use el procedimiento descripto más arriba y muestre en pantalla todos los S-términos generados.

Consideremos un cálculo con S-términos. La única regla algebraica (S-regla) que puede ser usada es la siguiente:

Cualquier subtérmino de un S-término que tenga la forma:

(((SA)B)C) donde A, B y C son S-términospuede ser reescrito como:

((AC)(BC))

Por ejemplo:

Contexto1(((SA)B)C)Contexto2 ----> Contexto1((AC)(BC))Contexto2

LLamaremos "reducción" a la aplicación de esta regla sobre un S-término.

Hay muchas formas (estrategias) de elegir subtérminos para aplicar la S-regla. La aplicación sucesiva de esta regla sobre un S-término hasta que no sea posible aplicarla nuevamente se llama "normalización" del S-término.

Ejemplo de reducciones sucesivas:

((((SS)(SS))S)(SS)) ----> (((SS)((SS)S))(SS)) ----> ((S(SS))(((SS)S)(SS))) ---->

((S(SS))((S(SS))(S(SS))))

2.- Elija una apropiada estructura de datos para representar los S-términos que pueda facilitarle la aplicación de la S-regla.Escriba luego dos porcedimientos "READTERM" y "PRINTERM":READTERM: que transforme el S-término en la representación que Ud. ha elegido.PRINTERM: que transforme la representación en un S-término de los generados por GENSTERM.

Su programa debe poder mostrar estas transformaciones.

3.- Escriba un procedimiento "REDUCE" para hacer un paso de reducción de acuerdo a la S-regla, sobre un S-subtérmino especificado de un S-término dado en su representación (la elegida por Ud.).

Su programa debe poder mostrar esto.

4.- Escriba un procedimiento "NORMALIZE": Dado un S-término, deberá elegir sucesivamente un subtérmino para aplicar la S-regla hasta que no pueda volver a aplicarla o bien hasta el número de veces que se haya aplicado sea mayor que 30.

Su programa debe poder mostrar esto.

5.- Finalmente, incorpore todo lo anterior en un programa que:

a) pida al usuario el ingreso (entrada) de un entero positivo n que indique la longitud

b) use los S-términos de longitud n generados por GENSTERM

c) transforme los S-términos en la representación que Ud. ha elegido

d) normalice (cuando sea posible)

e) muestre los S-términos normalizadosf) muestre el número de veces que se ha aplicado la s-regla para cada uno de los S-términos o bien un mensaje "NO NORMALIZADO" en caso de un fallida normalización de 30 pasos.

g) muestre el número de S-términos no normalizados vs. el número total de S-términos para la longitud n considerada.

Evaluación:

(1): 20 puntos

(2): 25 puntos

(3): 5 puntos

(4): 20 puntos

(5): 20 puntos

Jurado: 10 puntos (claridad, estilo, elegancia)

Problema 76: HORIZONTE

Un arquitecto necesita un programa que le dé el contorno del horizonte en distintos barrios de la ciudad en la que trabaja. Para su proyecto, puede considerar los distintos edificios como rectángulos apoyados sobre una misma línea. De esta manera cada edificio queda representado por dos puntos del plano, ambos en la misma recta horizontal, así, al dar los puntos (1 ; 1) y (4 ; 1) estaremos indicando el rectángulo de vértices:

(1 ; 0) (1 ; 1) (4 ; 1) (4 ; 0)

Veamos un ejemplo con varios edificios:

Edificio 1: (1 ; 1) (4 ; 1)

Edificio 2: (2,5 ; 6) (7 ; 6)

Edificio 3: (5 ; 4) (6 ; 4)

Edificio 4: (9 ; 3) (10 ; 3)

Edificio 5: (4,5 ; 5) (8 ; 5)

Edificio 6: (-1 ; 2) (1,5 ; 2)

Edificio 7: (0 ; 6,5) (1 ; 6,5)

El contorno del horizonte en este caso quedará determinado al unir con segmentos de recta, respetando el orden en que se escriben, los siguientes puntos:

(-1,0) (-1 ; 2) (0 ; 2) (0 ; 6,5) (1 ; 6,5) (1 ; 2) (1,5 ; 2) (1,5 ; 1) (2,5 ; 1) (2,5 ; 6) (7 ; 6) (7 ; 5) (8 ; 5) (8 ; 0) (9 ; 0) (9 ; 3) (10 ; 3) (10 ; 0)

El arquitecto necesita además calcular la medida de la superficie cubierta por los edificios. En el caso de nuestro ejemplo esta superficie mide exactamente 45,5.

Implemente un programa que:

1.- Lea del teclado:

- el número entero N de edificios

- para todo i entre 1 y N, los puntos (a(i),b(i)) y (c(i),d(i))

El programa deberá rechazar todas las entradas que no tengan sentido.

2.- Muestre en pantalla una sucesión de puntos de manera que, al trazar el segmento de recta que une cada un punto con su siguiente, quede determinado el contorno del horizonte.

3.- Muestre en pantalla la medida de la superficie cubierta por los edificios.

En el ejemplo dado, la salida en pantalla será:

CONTORNO:

(-1,0) (-1 ; 2) (0 ; 2) (0 ; 6,5) (1 ; 6,5) (1 ; 2) (1,5 ; 2) (1,5 ; 1) (2,5 ; 1) (2,5 ; 6) (7 ; 6) (7 ; 5) (8 ; 5) (8 ; 0) (9 ; 0) (9 ; 3) (10 ; 3) (10 ; 0)

AREA: 45,5

Problema 77: Islas en el mar (Bonn, Alemania, julio de 1992)

El mar está representado por una matriz de NxN. Cada isla es un asterisco '*' en esa matriz. La tarea consiste en reconstruir el mapa de las islas a partir, sólamente, de cierta información codificada sobre la distribución horizontal y vertical de las islas. Para ilustrar esta codificación, consideremos el siguiente mapa:

* * * 1 2

* * * * 3 1

* * * 1 1 1

* * * * * 5

* * * * 2 1 1

* 1

1 1 4 2 2 1

1 2 3 2

Los números a la derecha de cada fila representan el orden y la medida de los grupos de islas en esa fila. Por ejemplo, "1 2 " en la primera fila significa que esa fila contiene un grupo de una isla seguido por un grupo de dos islas siendo arbitraria la longitud del mar a izquierda y

derecha de cada grupo de islas. Análogamente, la secuencia "1 1 1" debajo de la primer columna significa que esta columna contiene tres grupos de una isla cada uno, etc.

Escriba un programa que repita los pasos siguientes, hasta que un archivo de entrada dado, conteniendo varios bloques de información, haya sido totalmente leido:

1.- Lea el siguiente bloque de información de un archivo de entrada ASCII (para la estructura de los datos en ese archivo, mire también los ejemplos que figuran luego) y muéstrelos en pantalla.

Cada bloque de información está compuesto de:

- la medida de la matriz cuadrada

- las informaciones sobre cada una de las filas seguidas de las de las columnas

- la información para cada fila o columna aparece en una sola línea como una sucesión de números separados por un espacio y terminada con un 0 (número cero).

2.- Reconstruya el mapa (o todos los mapas, en caso de que sea posible más de una soclución - vea Ejemplo 4) y lo/s muestre en pantalla.

3.- Agregue el o los mapas a un archivo de salida ASCII. Cada espacio entre islas estará representado por dos espacios. Cada isla estará representada por un asterisco '*' seguido de un espacio.Los distintos mapas, si los hubiese, que satisfacen las mismas restricciones deberán ser separados por una línea en blanco. Si no hubiese ningún mapa que satisfaga las restricciones, deberá indicar este hecho con una línea que diga "no map" (o sea, ningún

mapa).

Las soluciones a los diferentes bloques de información deberán ser separadas por una línea que diga "next problem" (o sea, próximo problema).

Restricciones técnicas:

Restricción 1: N debe ser no inferior a 1 y no mayor que 8.

Restricción 2: Ponga su programa solución en un archivo de texto ASCII

rotulado:

"413-PROG.xxx"

donde la extensión .xxx es:

- .BAS para programas BASIC

- .C para programas C

- .LCN para programas LOGO

- .PAS para programas PASCAL.

Restricción 3: El nombre para el archivo ASCII de entrada del cual se lee la información codificada debe ser:

"413-SEAS.IN"

Restricción 4: El nombre del archivo ASCII de salida para escribir el o los mapas debe ser:

"413-SEAS.OU"

EJEMPLOS:

Ejemplo 1: (correspondiente al mapa que figura al principio del enunciado)

6 <-- 6 es la medida de la matriz

1 2 0 <-- el comienzo de la información sobre filas

3 1 0

1 1 1 0

5 0

2 1 1 0

1 0

1 1 1 0 <-- el comienzo de la información sobre columnas

1 2 0

4 0

2 3 0

2 0

1 2 0

Ejemplo 2:

4 Solución: columnas: 1 2 3 4

0 fila 1:

1 0 fila 2: *

2 0 fila 3: * *

0 fila 4:

1 0

2 0

Ejemplo 3:

2 Note que no hay ningún mapa satisfaciendo las restricciones.

2 0

Ejemplo 4:

2 Note que hay dos mapas diferentes que satisfacen la información

1 0

Advertencia: La ejecución satisfactoria de su programa con estos ejemplos no garantiza que su programa sea correcto!!!!

Problema 78: Escalando una montaña (Bonn, Alemania, julio de 1992)

Un club de montañistas tiene P miembros numerados de 1 a P. Todos los miembros escalan con la misma velocidad y no hay diferencia de velocidad entre ascender y descender.

El montañista número i consume C(i) unidades de víveres por día y puede cargar, a lo sumo, S(i) de tales unidades. Los números C(i) y S(i) son enteros.

Suponga que un montañista, con suficiente cantidad de víveres, necesita N días para alcanzar la cima de la montaña. La montaña puede ser demasiado alta de manera tal que un solo montañista no pueda transportar los víveres necesarios. Un grupo de montañistas comienza a escalar en el mismo lugar y al mismo tiempo. Un montañista que desciende prematuramente, antes de alcanzar la cima, entrega a los otros montañistas los víveres que no necesitará. Los montañistas no descansan durante la expedición. No se puede almacenar comida en la montaña para usarla en el descenso.

El problema es planificar un cronograma para el club de montañistas. Por lo menos uno de los montañistas debe alcanzar la cima de la montaña y todos los montañistas del grupo selecciondo deben volver al punto de partida.

Implemete un programa que:

1.- Lea del teclado:

- el número entero N de días necesarios para llegar a la cima

- el número P de montañistas en el club y

- para todo i entre 1 y P, los números S(i) y C(i)

Ud. puede asumir que todas las entradas son enteros.

Rechace todas las entradas que no tengan sentido.

2.- Trate de encontrar un cronograma para escalar la montaña. Determine un grupo posible de escaladores a(1), ... , a(k) que debería participar en la excursión y, para todo j entre 1 y k, el número M(j) de víveres que el escalador a(j) carga en el momento de partir.

Observe que para algunas combinaciones de N, P, S(i) y C(i) podría no existir un cronograma.

3.- Muestre en pantalla la siguiente información:

a) el número k de los montañistas seleccionados para la excursión

b) la cantidad total de víveres necesarios

c) los números de los montañistas a(1), ... , a(k)

d) para cada a(j), j entre 1 y k, la cantidad inicial M(j) de víveres a cargar por el montañista a(j).

e) el día D(j) cuando el montañista a(j) empieza a descender

4.- Un cronograma es OPTIMO si:

a) el número de montañistas participantes es mínimo

b) entre todos los grupos que satisfagan la condición a) el total de víveres consumidos es mínimo.

Trate de encontrar un cronograma aproximadamente óptimo.

Restricciones técnicas:

Restricción 1: Ponga su programa solución en un archivo de texto ASCII rotulado "422-PROB.xxx".

La extensión .xxx debe ser:

- .BAS para programas BASIC

- .C para programas C

- .LCN para programas LOGO

- .PAS para programas PASCAL

Restricción 2: El programa debe rechazar los datos ingresados cuando N es menor que 1 o mayor que 100, o cuando P es menor que 1 o mayor que 20.

Ejemplos:

El siguiente podría ser un diálogo con su programa:

Días para llegar a la cima: 4

Número de miembros del club: 5

Capacidad de carga de víveres del montañista 1: 7

Consumo diario del montañista 1: 1

Capacidad de carga de víveres del montañista 2: 8

Consumo diario del montañista 2: 2

Capacidad de carga de víveres del montañista 3: 12

Consumo diario del montañista 3: 2

Capacidad de carga de víveres del montañista 4: 15

Consumo diario del montañista 4: 3

Capacidad de carga de víveres del montañista 5: 7

Consumo diario del montañista 5: 1

Se requieren 2 montañistas.

La cantidad total de víveres es 10.

Parten los montañistas: 1, 5

El montañista 1 carga 7 y desciende después de 4 día(s).

El montañista 5 carga 3 y desciende después de 1 día(s).

Planifica otra partida? (S/N): S

Días para llegar a la cima: 2

Número de miembros del club: 1

Capacidad de carga de víveres del montañista 1: 3

Consumo diario del montañista 1: 1

Imposible preparar un cronograma.

Planifica otra partida? (S/N): N

Hasta luego.

Advertencia: La ejecución satisfactoria de su programa con estos ejemplos no garantiza que su programa sea correcto!!!!

Problema 79:

En un país imaginario existen N mercados numerados de 1 a N y todos ellos están cerrados. Se suceden entonces N Ministros de Economía y cada uno de ellos decide "cambiar el estado" a algunos de los mercados. Cambiar el estado de un mercado quiere decir lo siguiente:

-si el mercado está abierto, lo cierra

-si está cerrado, lo abre.

Sin embargo los cambios de estado no son elegidos al azar pues obedecen a la siguiente regla:

El i-ésimo Ministro cambia de estado a todos los mercados cuyos números de orden son múltiplos de i.

Por ejemplo: el primer ministro abre todos los mercados.

el segundo cierra los múltiplos de dos (2, 4, 6, ...)

el tercero cierra a los múltiplos de 3 que no son múltiplos de 2 (3, 9, 15, ...) y abre a los que son múltiplos de 3 y 2 (6, 12, 18, ...).

Se trata entonces de hacer un programa que permita el ingreso del número N de mercados (que es idéntico al de ministros) y dé como resultado el estado final de cada uno de mercados. Sería conveniente que tratase de encontrar una justificación matemática para el resultado obtenido.

Problema 80:

El juego de los "cuadraditos" involucra a dos jugadores quienes, en su turno, unen puntos "consecutivos" en una grilla. Para armar la grilla se marcan en un papel 5 filas de cinco puntos cada una de la siguiente manera:

ø ø ø ø ø

Sólo se pueden trazar líneas horizontales o verticales entre dos puntos consecutivos. El jugador que "cierra" un cuadradito se anota un punto y tiene derecho a repetir su turno. El final del juego llega cuando no quedan más segmentos por trazar siendo el ganador, naturalmente, quien tenga mayor puntaje.

Las alternativas del juego pueden irse representando con matrices:

1ra. fila de la matriz: los 4 segmentos horizontales de la primera fila de puntos.

2da. fila de la matriz: los 5 segmentos verticales que pueden ser trazados entre la primer fila de puntos y la segunda.

9na. fila de la matriz: los 4 segmentos horizontales de la quinta fila de puntos.

En cada lugar de la matriz figurarán alguno de los valores siguientes:

A: segmento trazado por el jugador A

B: segmento trazado por el jugador B

0: segmento "libre" o "disponible"

(Dependiendo del lenguaje que Ud. use quizás deba completar con algún valor adicional el 5to. lugar de las filas impares).

Se presentarán así matrices como la siguiente:

A 0 B A

B A B B B

B B A A

A 0 A 0 0

0 0 0 B

B 0 0 0 0

B 0 A 0

0 A 0 0 A

0 0 0 B

1.- escriba un programa que permita ingresar una matriz del tipo mostrado arriba (que siempre representa una grilla 5x5) y determine el número de "cuadraditos" que ya tienen 3, y sólo 3, de sus lados dibujados. (En el ejemplo dado hay sólo uno de estos cuadraditos) emitiendo un mensaje del tipo:

La matriz contiene x cuadraditos de, exactamente, 3 lados dibujados.

2.- Modifique su respuesta al inciso 1) de manera de que la PC juegue en lugar de B y complete la mayor cantidad de cuadraditos posible con una sola jugada (teniendo en mente que el completar un cuadradito le da derecho a trazar un nuevo segmento dentro del mismo turno) mostrando en pantalla el mensaje siguiente:

P nuevos cuadraditos han sido completados

Ultimo segmento trazado = (F,C)

(donde F y C representan la fila y la columna del ultimo segmento trazado por la computadora).

Volver