661 - Triunghiuri1

Cerinţa

Se dau n numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n numere naturale.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând numărul de triunghiuri determinate.

Restricţii şi precizări

• 1 ⩽ n ⩽ 1000
• cele n numere citite vor fi mai mici decât 1.000.000

Exemplul 1

Intrare

5
3 5 10 7 6 

Iesire

Datele de intrare corespund restrictiilor impuse
7

Exemplul 2

Intrare

3
1 2 1000000000

Iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def numar_triunghiuri(n_val, numere_val):

   numere_val.sort()
   count = 0
   for i in range(n_val-2):
       k = i + 2
       for j in range(i+1, n_val):
           while k < n_val and numere_val[i] + numere_val[j] > numere_val[k]:
               k += 1
           if k > j:
               count += k - j - 1
   return count

def verifica_restrictii(n_val, numere_val):

   if n_val < 1 or n_val > 1000:
       return "Datele de intrare nu corespund restrictiilor impuse"
   for numar in numere_val:
       if numar >= 1000000:
           return "Datele de intrare nu corespund restrictiilor impuse"
   return "Datele de intrare corespund restrictiilor impuse"

n = int(input()) numere = list(map(int, input().split())) print(verifica_restrictii(n, numere)) print(numar_triunghiuri(n, numere)) </syntaxhighlight>

Explicație

Cele 7 triunghiuri au lungimile laturilor:

3 5 7
3 5 6
3 7 6
5 7 6
5 10 7
5 10 6
10 7 6