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

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.")