OLI 2024, Brașov, clasa a X-a · Clasa a X-aStructuri de date liniareProbleme cu coadă
Problema Parc
Primăria Brașov vrea să amenajeze un parc de divertisment pentru cetățenii orașului. Cum suntem la munte, zona în care urmează a fi amenajat acest parc este denivelată. Despre fiecare bucată de 10 x 10 m știm altitudinea medie (luată relativ cu un reper ales de proiectanți). În acest parc se dorește a se amenaja mai multe lacuri astfel: se alege un număr L, iar toate zonele ce au înălțimea (strict) sub acest L vor fi umplute de apă. Cum încă nu sunt siguri cu privire la cum vor să amenajeze parcul, sunteți rugați să ajutați prin răspunderea la următoarele cerințe.
Cerință
Știind harta parcului (de N x M), avem de răspuns la trei întrebări:
- Pentru o zonă dată și un nivel
L, câte lacuri vor fi formate? - Pentru o zonă dată, care este nivelul minim
Lcare ar trebui ales pentru a avea un singur lac? - Pentru o zonă dată, ce nivel
Lar trebui ales pentru a avea un număr cât mai egal de parcele acoperite de apă și parcele neacoperite de apă (diferența în modul dintre cele două să fie minimă)?
Date de intrare
Fișierul de intrare parc.in conține pe prima linie un singur număr natural C, care reprezintă cerința de rezolvat. A doua linie a fișierului conține două numere naturale separate printr-un spațiu N și M, care reprezintă dimensiunile matricei ce reprezintă harta parcului. Următoarele N linii conțin câte M numere naturale separate prin câte un spațiu ce reprezintă elementele matricei ce reprezintă denivelările parcului. În cazul în care C este 1, pe următoarea linie se află numărul L, reprezentat nivelul până la care se umple cu apă.
Date de ieșire
Fișierul de ieșire parc.out va conține o linie astfel:
- Dacă
C = 1, atunci se va rezolva doar punctul 1 din cerință: Se va afișa un singur număr natural reprezentând numărul de lacuri formate. - Dacă
C = 2, atunci se va rezolva doar punctul 2 din cerință: Se va afișa un singur număr natural, reprezentând nivelul necesar pentru a forma un singur lac. - Dacă
C = 3, atunci se va rezolva doar punctul 3 din cerință: Se va afișa un singur număr natural, reprezentând nivelul necesar pentru a forma diferența în modul dintre numărul de parcele acoperite și parcele neacoperite minimă.
Restricții și precizări
1 ≤ C ≤ 31 ≤ N, M ≤ 1000- 20% din teste au
C = 1, 30% din teste auC = 2, iar restul de 50% auC = 3 - Un lac se consideră ca fiind format doar din elemente adiacente pe cele
4direcții:N, S, E, V 0 ≤ elementele din matrice ≤ 109
Exemple
1 3 5 2 1 3 4 5 3 9 4 7 3 2 9 1 9 3 5
2
2 3 5 2 1 3 4 5 3 9 4 7 3 2 9 1 9 3
6
3 3 5 2 1 3 4 5 3 9 4 7 3 2 9 1 9 3
4
Explicația exemplelor
Pentru primul exemplu. După umplerea zonelor care se află la un nivel mai mic de 5, parcul arată astfel:
Pentru al doilea exemplu. Pentru L = 6, parcul arată (cu bold sunt zonele neacoperite de apă):
Pentru al treilea exemplu. Cel mai mare nivel pentru care numărul de zone acoperite de apă este mai mic decât numărul de zone neacoperite este L = 3 (cu bold sunt zonele neacoperite de apă):
Astfel diferența în modul dintre numărul de parcele acoperite și cele neacoperite este |nracoperite - nrneacoperite| = |4 - 11| = 7.
Pentru L = 4:
Astfel diferența devine: |nracoperite - nrneacoperite| = |8 - 7| = 1.
Astfel, cel mai mare număr pentru care diferența minimă este 4.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;