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

<syntaxhighlight lang="python" line> 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()

</syntaxhighlight>