Editing 0698 - nrpits (section)

= 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>