
ATENTIE: asteptam rezolvari originale, nu copiate de la colegi!
(ne cerem scuze celor carora nu se adreseaza mesajul de mai sus)

Etapa contine doua probleme.

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

Problema 1: Impaturirea hartilor (45 puncte)

    O harta strategica este reprezentata ca o matrice cu n linii si m
coloane (1<=n , m<=100) fiecare componenta a matricii continand cota zonei
de teren corespunzatoare exprimata in metri de la nivelul marii, cota fiind
un numar natural. Determinati o modalitate de a impaturi harta astfel incat
deasupra sa se gaseasca o zona de arie maxima avand aceeasi cota. Plierea
hartii se poate face doar orizontal si vertical ( deci pe directii paralele
cu laturile hartiei ) si numai cu doua parti egale ( deci daca o dimensiune
a hartiei este impara, plierea de-a lungul laturii respective nu este
posibila ) . Pe ecran se va afisa aria zonei astfel determinate, cota
corespunzatoare, precum si codificarea sirului de plieri efectuate, folosind
urmatoarea conventie : se precizeaza mai intai directia ( H-orizontal
; V-vertical ) , apoi pozitia de la care se face plierea, apoi modul
de pliere ( L-partea stanga deasupra ; R-partea dreapta
deasupra ; U-partea de sus deasupra ; D-partea de jos deasupra
) , doua plieri consecutive fiind separate prin spatiu. Daca problema nu are
solutie se va afisa mesajul "Ghinion".
Restrictii de intrare/iesire : 
   Numele fisierului se va citi del a tastatura. Fisierul de intrare
contine pe prima linie n si m , dimensiunile hartiei ,
separate printr-un spatiu , iar pe urmatoarele n linii cate m
numere naturale care reprezinta cotele . 
   Fisierul de iesire se va numi harta.out si va contine :
   pe prima linie mesajul "Aria maxima" urmat de valoarea maxima a zonei de teren determinate
   pe a doua linie mesajul "Cota" urmat de valoarea cotei comune zonei determinate
   pe a treia linie codificarea sirului de plieri

sau

   mesajul "Ghinion", daca problema nu are solutie.

   Exemplu:

Pentru fisierul de intrare :

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

Fisierul de iesire va contine mesajul "Ghinion"

Pentru fisierul de intrare :

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

Fisierul de iesire poate fi :

  Aria maxima 4
  Cota 1
  H2U H1U

sau

  Aria maxima 4
  Cota 2
  H3D H4D


   Atentie ! Daca exista mai multe solutii se va afisa una singura !

Timp de executie 30 sec/test.

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

       VARFURILE UNOR FIGURI GEOMETRICE (30 puncte)

  Se considera punctele unei matrici infinite de triunghiuri echilaterale
ca cele de mai jos:

                                      1
                                    /   \
                                   2 --- 3
                                 /   \ /   \  
                                4 --- 5 --- 6
                              /   \ /   \ /   \
                             7 --- 8 --- 9 --- 10
                            /  \  /  \  /  \  /   \
                          11 -- 12 -- 13 -- 14 -- 15
                         /   \  /  \  /  \  /  \  /  \ 
                       16 -- 17 -- 18 -- 19 -- 20 -- 21
                      /  \   /  \  /  \  /  \  /  \  /  \ 
                     22 -- 23 -- 24 -- 25 -- 26 -- 27 -- 28          
        		. . . . . . . . . . . . . .			

	Observati ca grupuri ale acestor puncte formeaza varfurile unor
forme geometrice. 
	De exemplu:
{1,2,3} si {7,9,11} sunt varfurile unor triunghiuri
{11,13,26,24} si {2,7,9,18} sunt varfurile unor paralelograme
{4,5,9,13,12,7} si {8,10,17,21,32,34} sunt varfurile unor hexagoane 

	Scrieti un program care sa citeasca mai multe seturi de date,
sa le analizeze si sa hotarasca daca punctele sunt varfurile unei figuri
geometrice: triunghi, paralelogram sau hexagon. Pentru ca o figura sa fie 
corecta, trebuie sa indeplineasca urmatoarele conditii:
 1. fiecare latura sa coincida cu o muchie a matricii
 2. laturile figurii sa fie congruente

	Citirea se face din fisierul "input" care contine mai multe seturi
de date, fiecare set pe o linie. Exista cel mult 6 numere pe o linie, 
cuprinse in intervalul 1..32767.
	Rezultatul se tipareste in fisierul "output" si consta in listarea 
numerelor urmate de rezultatul analizei.

	Exemplu:

fisierul "input":
1 2 3
11 13 29 31
26 11 13 24
4 5 9 13 12 7
1 2 3 4 5 
47
11 13 23 25
 
fisierul "output":
1 2 3 sunt varfurile unui triunghi
11 13 29 31 nu sunt varfurille unei figuri acceptabile
26 11 13 24 sunt varfurile unui paralelogram
4 5 9 13 12 7 sunt varfurile unui hexagon
1 2 3 4 5 nu sunt varfurile unei figuri acceptabile
47 nu sunt varfurile unei figuri acceptabile
11 13 23 25 nu sunt varfurile unei figuri acceptabile


Timp de executie 30 sec/test.   

                                            Concurs ACM 1991


