0660 - Triunghiuri

Sursa: 0660 - Triunghiuri

---

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

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

Restricţii şi precizări

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

Exemple

Exemplul 1

Intrare

5

3 5 10 7 6

Ieșire

Datele sunt introduse corect.

7

Exemplul 2

Intrare

5

2 3 1 -2 5

Ieșire

Datele nu corespund restricțiilor impuse.

Explicație exemplul 2

Laturile unui triunghi trebuie să fie numere naturale. -2 nu este număr natural, așadar nu respectă restricțiile.

Rezolvare

<syntaxhighlight lang="python" line>

1. 0660-Triunghiuri

def nr_triunghiuri_distincte(vector, n):

   C = 0
   for i in range(n):
       for j in range(i + 1, n):
           for k in range(j + 1, n):
               latura1 = vector[i]
               latura2 = vector[j]
               latura3 = vector[k]
               if latura1 + latura3 > latura2 and latura1 + latura2 > latura3 and latura2 + latura3 > latura1:
                   C += 1
   print(C)

def citire_conform_restrictiilor(vector, n):

   if n < 1 or n > 100:
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   for element in vector:
       if element >= 1000000 or element < 0:
           print("Datele nu corespund restricțiilor impuse.")
           exit()
   if n != len(vector):
       print("Datele nu corespund restricțiilor impuse.")
       exit()
   print("Datele sunt introduse corect.")

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   citire_conform_restrictiilor(vector, n)
   nr_triunghiuri_distincte(vector, n)

</syntaxhighlight>

Explicație rezolvare

   Programul de mai sus conține două funcții, funcția nr_triunghiuri_distincte(vector, n) și funcția citire_conform_restrictiilor(vector, n), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 30) după citirea numărului n (linia 31) și celor n numere pe care le vom pune în șirul „vector” (linia 32).
   După ce am citit elementele, se va apela funcția citire_conform_restrictiilor(vector, n) care primește doi parametri: vectorul „vector” și lungimea sa, reprezentată de variabila „n”. Funcția verifică dacă lungimea vectorului n este între 1 și 100 (linia 17), dacă elementele vectorului sunt mai mici decât 1000000, respectiv mai mari decât 0 (liniile 20, 21, laturile unui triunghi trebuie să fie valori pozitive) și dacă n este lungimea vectorului „vector” (linia 24). Dacă oricare dintre condiții este încălcată, se va afișa mesajul „Datele nu corespund restricțiilor impuse.” și se va ieși din program cu comanda exit(). Dacă toate condițiile sunt respectate, se va afișa mesajul „Datele sunt introduse corect.” (linia 27) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția nr_triunghiuri_distincte(vector, n) care primește ca parametrii vectorul „vector” și dimensiunea sa „n”. În această funcție se inițializează variabila C (notată C conform problemei) cu 0. În continuare, se parcurge vectorul cu trei bucle for (liniile 5-7) pentru a itera prin toate combinațiile posibile de trei laturi din vector. Apoi, se iau cele trei laturi din vector (pe care le punem în variabilele latura1, latura2 și latura 3) și se verifică dacă pot forma un triunghi valid folosind inegalitatea triunghiului care spune că un triunghi are mereu, prin toate combinațiile, două laturi adunate mai mari decât cea rămasă. Verificăm acest fapt pe linia 11, iar dacă toate combinațiile de laturi respectă regula, atunci am găsit un triunghi și marcăm acest fapt prin incrementarea numărul C cu 1. După terminarea tuturor for-urilor, avem numărul total de triunghiuri distincte în numărul C, pe care îl afișăm, terminând problema.