3201 - IJK

Cerinţa

Se dă un şir a cu n numere naturale. Aflaţi numărul tripletelor (i,j,k), cu 1 ≤ i < j < k ≤ n, pentru care avem a[i] > a[j] < a[k].

Date de intrare

Fișierul de intrare ijk.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire ijk.out va conține pe prima linie numărul tripletelor (i,j,k), cu 1 ⩽ i < j < k ⩽ n, pentru care avem a[i] > a[j] < a[k]'.

Restricţii şi precizări

• 3 ⩽ n ⩽ 70.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 2.000.000.000

Exemplul 1

ijkin.txt

5
3 11 2 7 14

ijkout.txt

5

Explicatie

Tripletele cu proprietatea cerută sunt: (1,3,4), (1,3,5), (2,3,4), (2,3,5), (2,4,5).

Exemplul 2

ijkin.txt

1
1000000000

ijkout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

def verifica_restrictii(n, a):
    if n < 3 or n > 70000:
        return False
    for numar in a:
        if numar < 0 or numar >= 2000000000:
            return False
    return True

def calculeaza_triplete(n, a):
    numar_triplete = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if a[i] > a[j] and a[j] < a[k]:
                    numar_triplete += 1
    return numar_triplete

def rezolva_problema():
    with open('ijkin.txt', 'r') as fisier_intrare:
        n = int(fisier_intrare.readline())
        a = list(map(int, fisier_intrare.readline().split()))

    if verifica_restrictii(n, a):
        print("Datele de intrare corespund restrictiilor impuse")
        numar_triplete = calculeaza_triplete(n, a)

        with open('ijkout.txt', 'w') as fisier_iesire:
            fisier_iesire.write(str(numar_triplete))
    else:
        print("Datele de intrare nu corespund restrictiilor impuse")

rezolva_problema()