Etapa 4: 5 februarie 1997

Problema 1
Problema 2
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 !

prof. Emanuela Mateescu
Liceul de Informatica "Grigore Moisil" Iasi

Problema 2: Concurs (45 puncte)


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


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 cuntine 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 varfurile 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

Concurs ACM 1991

[Index] [Informatii importante!] [Participanti] [Etapa 3] [Etapa 5]