ID #123 · Colecția InfoAs · Operatori și expresii

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: 1. Pentru o zonă dată și un nivel `L`, câte lacuri vor fi formate? 2. Pentru o zonă dată, care este nivelul minim `L` care ar trebui ales pentru a avea un singur lac? 3. Pentru o zonă dată, ce nivel `L` ar 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: 1. 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. 2. 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. 3. 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 ≤ 3` * `1 ≤ N, M ≤ 1000` * 20% din teste au `C = 1`, 30% din teste au `C = 2`, iar restul de 50% au `C = 3` * Un lac se consideră ca fiind format doar din elemente adiacente pe cele `4` direcții: `N, S, E, V` * `0 ≤ elementele din matrice ≤ 10<sup>9</sup>`