0698 - nrpits

Enunt

Se dă un șir de N numere distincte a[1],a[2],..a[N]. Orice secvență a[i],a[i+1],...,a[j-1],a[j], 1 ≤ i + 1 < j ≤ n, pentru care toate valorile a[k], i < k < j, sunt mai mici decât extremitățile a[i] și a[j], o vom numi în continuare “groapă”.

Cerința

Scrieţi un program care va determina numărul “gropilor” din șirul dat.

Date de intrare

Fișierul de intrare nrpits.in conţine pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere naturale ale șirului, separate prin spațiu.

Date de ieșire

Fișierul de ieșire nrpits.out va conține un singur număr reprezentând numărul de “gropi” ale șirului dat.

Restricții și precizări

• 2 ≤ N ≤ 1.000.000
• 1 ≤ a[i] ≤ 1.000.000, pentru fiecare 1 ≤ i ≤ N
• orice “groapă” are cel puțin trei elemente

Exemplul 1

intare

12

12 1 10 3 4 11 5 8 7 9 2 6

iesire

Datele introduse corespund restrictiilor impuse.

8

Exemplul 2

intrare

1

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

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

1. 0698 - nrpits

def numar_gropi(serie):

   n = len(serie)
   grope = 0

   for i in range(1, n-1):
       valoare_curenta = serie[i]

       # Verificăm dacă este o groapă
       if serie[i-1] > valoare_curenta < serie[i+1]:
           grope += 1

   return grope

</syntaxhightlight>