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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." și programul va afișa pe ecran numărul C, reprezentând numărul de triunghiuri determinate. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

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  # Verificăm dacă input-ul este un număr valid între 1 și 1000.

def triunghiuri1(n, lat):

   lat.sort()  # Sortăm lista de lungimi de laturi în ordine crescătoare.
   cnt = 0  # Inițializăm contorul la 0.
   for i in range(n - 2):  # Parcurgem lista până la penultimul element.
       for j in range(i + 1, n - 1):  # Parcurgem sublista începând de la al doilea element până la penultimul.
           a = lat[i]  # Alegem prima latură a triunghiului ca fiind elementul de pe poziția i în lista sortată.
           b = lat[j]  # Alegem a doua latură a triunghiului ca fiind elementul de pe poziția j în lista sortată.
           dr = n - 1  # Setăm indicele dreptului pe ultimul element din listă.
           st = j + 1  # Setăm indicele stângului pe poziția imediat următoare după j.
           while dr >= st:  # Cat timp dreapta nu a depășit stânga în parcurgerea listei.
               mij = (dr + st) // 2  # Calculăm mijlocul listei.
               if lat[mij] < a + b:  # Dacă suma celor trei laturi formează un triunghi valid.
                   st = mij + 1  # Avansăm în dreapta pentru a căuta valori mai mari care să formeze triunghiuri.
               else:
                   dr = mij - 1  # Altfel, avansăm în stânga pentru a căuta valori mai mici care să formeze triunghiuri.
           cnt += dr - j  # Adăugăm la contor diferența între dreapta și j, care reprezintă numărul de triunghiuri posibile.

   print(cnt)  # Afișăm rezultatul.

if __name__ == '__main__':

   x = None  # Inițializăm x la None.
   n = input()  # Citim valoarea lui n de la tastatură.
   lat = list(map(int, input().split()))  # Citim lista de lungimi de laturi de triunghi și o convertim la tipul int.
   if validare(n):  # Verificăm dacă valoarea introdusă corespunde restricțiilor impuse.
       for i in range(int(n)):  # Parcurgem valorile de la 0 la n-1.
           if str(i).isdigit() and i < 1_000_000:  # Verificăm dacă i este un număr valid și nu depășește 1_000_000.
               x = True  # Dacă da, x devine True.
           else:
               x = False  # Altfel, x devine False.
       if x is True
           print("Datele introduse corespund restricțiilor impuse.")
           n = int(n)  # Convertim n la tipul int pentru a-l folosi în funcția triunghiuri1.
           triunghiuri1(n, lat)  # Apelăm funcția triunghiuri1 pentru a calcula numărul de triunghiuri posibile.
       else:
           print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>