0661 - Triunghiuri1

Cerință

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 de precizări

• 1 ⩽ n ⩽ 1000

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

Exemplu

Exemplul 1

Intrare

5

3 5 10 7 6

Ieșire

Datele introduse corespund restricțiilor impuse.

7

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1"> def validare(n):

   return n.isdigit() and 1 <= int(n) <= 1000

def triunghiuri1(n, lat):

   lat.sort()
   cnt = 0
   for i in range(n - 2):
       for j in range(i + 1, n - 1):
           a = lat[i]
           b = lat[j]
           dr = n - 1
           st = j + 1
           while dr >= st:
               mij = (dr + st) // 2
               if lat[mij] < a + b:
                   st = mij + 1
               else:
                   dr = mij - 1
           cnt += dr - j

   print(cnt)

if __name__ == '__main__':

   x = None
   n = input()
   lat = list(map(int, input().split()))
   if validare(n):
       for i in range(int(n)):
           if str(i).isdigit() and i < 1_000_000:
               x = True
           else:
               x = False
       if x is True:
           print("Datele introduse corespund restricțiilor impuse.")
           n = int(n)
           triunghiuri1(n, lat)
       else:
           print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>