Editing 0698 - nrpits

== Enunt ==

Se dă un șir de <code>N</code> numere distincte <code>a[1],a[2],..a[N]</code>. Orice secvență <code>a[i],a[i+1],...,a[j-1],a[j]</code>, <code>1 ≤ i + 1 < j ≤ n</code>, pentru care toate valorile <code>a[k]</code>, <code>i < k < j</code>, sunt mai mici decât extremitățile <code>a[i]</code> și <code>a[j]</code>, 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 <code>nrpitsIN.txt</code> 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 <code>nrpitsOUT.txt</code> va conține un singur număr reprezentând numărul de “gropi” ale șirului dat. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

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

= Exemplul 1: =
<code>nrpitsIN.txt</code>
 12
 12 1 10 3 4 11 5 8 7 9 2 6
<code>nrpitsOUT.txt</code>
 8

= Explicație =
Cele opt “gropi” sunt:

<code>12 1 10</code>

<code>10 3 4</code>

<code>12 1 10 3 4 11</code>

<code>10 3 4 11</code>

<code>11 5 8</code>

<code>8 7 9</code>

<code>9 2 6</code>

<code>11 5 8 7 9</code>

== Exemplul 2: ==
<code>nrpitsIN.txt</code>
 1000001
 12 1 10 3 4 11 5 8 7 9 2 6
<code>nrpitsOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricții(n, v):
    # Verificăm dacă N respectă restricțiile
    if not (2 <= n <= 1_000_000):
        return False
    # Verificăm dacă fiecare element din v respectă restricțiile
    for val in v:
        if not (1 <= val <= 1_000_000):
            return False
    return True

def main():
    with open("nrpitsIN.txt", "r") as fin:
        n = int(fin.readline())
        v = list(map(int, fin.readline().split()))

    # Verificăm restricțiile
    if not verifica_restricții(n, v):
        with open("nrpitsOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return  # Oprim execuția dacă datele nu respectă restricțiile

    # Continuăm procesarea datelor deoarece acestea respectă restricțiile
    v = [0] + v
    st = [-1] * (n + 1)
    dr = [-1] * (n + 1)

    s = []
    for i in range(1, n + 1):
        while s and v[i] > v[s[-1]]:
            s.pop()
        if s:
            st[i] = s[-1]
        s.append(i)

    d = []
    for i in range(n, 0, -1):
        while d and v[i] > v[d[-1]]:
            d.pop()
        if d:
            dr[i] = d[-1]
        d.append(i)

    ans = sum(1 for i in range(1, n + 1) if st[i] != -1 and dr[i] != -1)

    with open("nrpitsOUT.txt", "w") as fout:
        fout.write(str(ans))

if __name__ == "__main__":
    main()

</syntaxhighlight>