|
|
| Line 1: |
Line 1: |
| == Cerinta ==
| |
| În junglă cresc foarte mulți copaci, de diferite înălțimi. Fiind pasionat de copacii din junglă, Gigel a notat pe o foaie înălțimile la care pot ajunge copacii din junglă. Fiind închis în casă, își pune, ca orice copil normal, tot felul de întrebări bizare. El s-a gandit să planteze pomii în linie, într-o anumită ordine, și astfel a obținut N numere, v[1], v[2], ..., v[N], unde V[i] reprezintă înălțimea copacului i. Apoi i-au venit în minte două întrebări.
| |
|
| |
|
| Mai întâi vrea sa afle câți copaci plantați înaintea copacului cu numărul de ordine i au înălțimile mai mici ca acesta.
| |
|
| |
| A doua întrebare este mai speciala; Gigel se întreabă care ar fi dreptunghiul cu suprafața maximă liberă (adică neocupată de vreun copac) dacă ar încadra copacii într-o seră cu înălțimea egală cu înălțimea celui mai înalt copac plantat. Putem vizualiza sera ca pe un tablou bidimensional, cu colțul din stanga jos de coordonate (1,1) , iar cel din dreapta sus de coordonate (N,H), unde N este numărul de copaci, iar H este înâlțimea maximă a unui copac. În acest tablou copacul cu numărul de ordine i ocupă primele v[i] unități de pe coloana i, de jos in sus (v[i] reprezintă înălțimea copacului i).
| |
|
| |
| == Date de intrare ==
| |
| Programul citește de la tastatură un număr p, care poate avea valorile 1 sau 2, în funcție de cerința problemei.
| |
|
| |
| Pentru p = 1, următorul rând conține numerele N q. Următorul rând conține n valori, a i -a valoare reprezentând înălțimea copacului cu numarul de ordine. Rândul următor conține q numere; pentru fiecare număr i se cere numarul de copaci plantați înaintea copacului cu numărul de ordine i cu înălțimi mai mici ca acesta.
| |
|
| |
| Pentru p = 2, următorul rând va conține doar numărul N, iar ultimul rând va conține N valori reprezentând înălțimile copacilor.
| |
|
| |
| == Date de iesire ==
| |
| Pentru p = 1 programul va afișa q linii; pe fiecare linie se va afla raspunsul pentru fiecare dintre cele q numere date.
| |
|
| |
| Pentru p = 2 programul fa afișa singur numar, reprezentând raspunsul pentru cerinta 2 , adică dreptunghiul liber de arie maximă.
| |
|
| |
| == Restricti1 si precizari ==
| |
| *Pentru cerința 1, n ≤ 1000, iar pentru cerința 2, n ≤ 100.000
| |
| *înâlțimile copacilor vor fi numere naturale nenule mi mai mici decât 15.000
| |
| *1 ≤ q ≤ 2*n
| |
| *Pentru 25 de puncte cerința este 1.
| |
|
| |
| == Exemplu 1 ==
| |
|
| |
| ;intrare
| |
| :1
| |
| :7 3
| |
| :4 2 6 8 3 4 2
| |
| :2 4 6
| |
|
| |
| ;iesire
| |
| ;Datele introduse corespund restrictiilor impuse
| |
| :0
| |
| :3
| |
| :2
| |
|
| |
|
| |
| == Exemplul 2 ==
| |
|
| |
| ;intrare
| |
|
| |
| :3
| |
|
| |
| :12
| |
|
| |
| :7 8 9 9 11 9 6 7 2 1 3
| |
|
| |
| ;iesire
| |
|
| |
| ;Datele de intrare nu corespund restrictiilor impuse
| |
|
| |
| == Rezolvare ==
| |
| <syntaxhighlight lang="python3"line="1">
| |
| def copaci_cu_inaltimi_mici(v):
| |
| n = len(v)
| |
| cnt_copaci_mici = [0] * n
| |
|
| |
| for i in range(1, n):
| |
| for j in range(i):
| |
| if v[i] > v[j]:
| |
| cnt_copaci_mici[i] += 1
| |
|
| |
| return cnt_copaci_mici
| |
|
| |
|
| |
| def suprafata_maxima_liber(v):
| |
| n = len(v)
| |
| stiva = []
| |
| max_suprafata = 0
| |
|
| |
| for i in range(n):
| |
| while stiva and v[i] <= v[stiva[-1]]:
| |
| h = v[stiva.pop()]
| |
| w = i if not stiva else i - stiva[-1] - 1
| |
| max_suprafata = max(max_suprafata, h * w)
| |
| stiva.append(i)
| |
|
| |
| while stiva:
| |
| h = v[stiva.pop()]
| |
| w = n if not stiva else n - stiva[-1] - 1
| |
| max_suprafata = max(max_suprafata, h * w)
| |
|
| |
| return max_suprafata
| |
|
| |
| </syntaxhighlight>
| |
