Creasta unui tablou bidimensional

Subprogramul care întoarce coloana vârfului dacă linia este munte, și programul C++ care verifică dacă vârfurile tuturor liniilor formează o creastă.

📋 Enunț

Un șir de numere naturale este numit munte dacă există un termen al său, numit vârf, cu proprietatea că este strict mai mare decât toți ceilalți termeni ai șirului și că secvența formată din toți termenii care îl preced în șir, dacă există, este strict crescătoare, iar secvența formată din toți termenii care îi urmează în șir, dacă există, este strict descrescătoare.

Subprogramul varf are trei parametri:

n, prin care primește un număr natural (n ∈ [2,50]);
a, prin care accesează un tablou bidimensional cu n linii și n coloane, numerotate de la 1 la n, cu elemente numere naturale din intervalul [0, 10⁹];
k, prin care primește un număr natural (k ∈ [1,n]).

Subprogramul returnează numărul coloanei pe care se află vârful șirului memorat pe linia k, dacă acesta este munte, sau valoarea 0 în caz contrar.

Exemplu: pentru n=7 și tabloul de mai jos, dacă k=3, subprogramul returnează 5, iar dacă k=6, subprogramul returnează 0.

Într-un tablou bidimensional se formează o creastă dacă pe fiecare linie șirul memorat este munte și dacă, pentru oricare două linii consecutive, vârfurile se află pe aceeași coloană sau pe coloane consecutive.

Se citesc de la tastatură un număr natural, n (n ∈ [2,50]), și n·n numere naturale din intervalul [0, 10⁹], elemente ale unui tablou bidimensional cu n linii și n coloane, numerotate de la 1 la n.

Se cere să se afișeze pe ecran mesajul DA, dacă în tabloul citit se formează o creastă, sau mesajul NU în caz contrar.

Exemplu: pentru n=7 și elementele tabloului de mai jos, se afișează pe ecran NU.

0 1 2 4 2 1 0
3 4 5 7 8 4 2
0 1 2 3 8 2 1
0 1 3 4 5 6 7
1 2 3 4 5 6 5
3 2 1 5 3 4 4
2 3 4 9 6 3 2

Scrieți programul Pascal/C/C++ corespunzător cerinței, care să cuprindă definiția completă a subprogramului precizat mai sus, precum și apeluri utile ale acestuia.

Ce înseamnă că un șir este munte

Definiția cere trei lucruri deodată: vârful să fie strict mai mare decât toți ceilalți termeni, partea dinaintea lui să crească strict, iar partea de după el să scadă strict.

Prima condiție are o consecință care simplifică rezolvarea: vârful este maximul șirului, iar acest maxim este unic. Dacă valoarea maximă ar apărea de două ori, niciuna dintre apariții nu ar fi strict mai mare decât cealaltă, deci șirul nu ar fi munte.

Șirul poate începe chiar cu vârful sau se poate încheia cu el — enunțul spune „dacă există” tocmai pentru aceste cazuri. Un șir strict crescător este munte, cu vârful pe ultima poziție; unul strict descrescător este munte, cu vârful pe prima.

Verificarea se face deci în trei pași: se determină poziția maximului, se verifică creșterea strictă până la ea și se verifică descreșterea strictă după ea. Nu mai este nevoie de o verificare separată a unicității maximului: dacă maximul apare de mai multe ori, una dintre cele două parcurgeri întâlnește două valori egale alăturate și se oprește.

Descrierea algoritmului în limbaj natural

Se citesc dimensiunea n și cele n·n elemente ale tabloului.

Pentru fiecare linie k se apelează subprogramul varf. În interiorul lui se determină mai întâi poziția celui mai mare element de pe linie, parcurgând linia de la stânga la dreapta și reținând poziția primei apariții a maximului. Se parcurge apoi partea dinaintea acestei poziții și se verifică dacă fiecare element este strict mai mare decât cel dinaintea lui; dacă nu, subprogramul returnează 0. Se parcurge partea de după poziția maximului și se verifică dacă fiecare element este strict mai mic decât cel dinaintea lui; dacă nu, se returnează tot 0. Dacă amândouă verificările trec, se returnează poziția maximului.

În programul principal se rețin valorile întoarse pentru cele n linii. Dacă vreuna dintre ele este 0, o linie nu este munte, deci tabloul nu formează creastă și se afișează NU.

Dacă toate liniile sunt munți, se verifică a doua condiție: pentru fiecare pereche de linii consecutive, diferența dintre coloanele vârfurilor trebuie să fie, în valoare absolută, cel mult 1 — aceasta este scrierea condiției „pe aceeași coloană sau pe coloane consecutive”. Dacă o pereche nu o îndeplinește, se afișează NU.

Dacă amândouă condițiile sunt îndeplinite pentru tot tabloul, se afișează DA.

Rezolvarea se poate citi pe educamp.ro, la adresa de mai sus.

Ce cuprinde rezolvarea

Ce înseamnă că un șir este munte
Descrierea algoritmului în limbaj natural
Programul
Verificarea pe exemplul din enunț

Vezi rezolvarea ca și cursant

Cel puțin o cerință din fiecare an este disponibilă gratuit și integral. Pentru a citi toate celelalte rezolvări ale disciplinei, te înscrii la cursul de pregătire.

Cursul cuprinde suportul de curs publicat până acum, care se completează capitol cu capitol, și două întâlniri de câte două ore în fiecare lună. Prima săptămână este gratuită, fără plată și fără card. Dacă vrei să vezi mai întâi cum este scrisă o rezolvare, poți reveni la prima cerință a anului.

Începe săptămâna gratuită Sunt cursant — login

Ce înseamnă că un șir este munte

Descrierea algoritmului în limbaj natural

Ce cuprinde rezolvarea

🔒 Vezi rezolvarea ca și cursant

Vezi rezolvarea ca și cursant