← Subiecte de Titularizare
Titularizare 2024 · Subiectul II, problema 1

Matrice — munte și creastă — simulator

II.1 subprogram Liste Șiruri caractere Matrice Backtracking
II.2 eficient Greedy intervale Reuniune Interclasare LIS LIS tije LCS Kadane Frecvențe Căutare binară
pas 0 / 0
📋 Enunțul problemei (Titularizare 2024)

Un șir e munte dacă are un termen (vârful) strict mai mare decât toți ceilalți, secvența dinaintea lui e strict crescătoare, iar cea de după el strict descrescătoare. (Oricare dintre cele două părți poate lipsi.)

Subprogramul varf(n, a, k) returnează numărul coloanei pe care se află vârful șirului de pe linia k, dacă acesta e munte, sau 0 altfel.

Într-o matrice se formează o creastă dacă fiecare linie e munte și, pentru oricare două linii consecutive, vârfurile sunt pe aceeași coloană sau pe coloane alăturate.

Exemplu: pentru matricea de mai jos se afișează NU. Din barem: varf(k=3) = 5, varf(k=6) = 0.

startApasă „Pas înainte”. Pentru fiecare linie: urc cât se poate, verific că coborârea e strictă, apoi compar vârful cu cel de pe linia dinainte.

Matricea 7×7 ultima coloană: vârful fiecărei linii

urcuș strict vârful coborâre strictă strică proprietatea creasta (vârfurile)

Starea algoritmului linia curentă

Codul C++ linia activă e evidențiată

Cod C++

    

Algoritmul în limbaj natural pasul curent e evidențiat