Fișierul intrare/ieșire | nrtri2.in, nrtri2.out | Sursă | Problema nrtri |
---|---|---|---|
Autor | Radu Voicu | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.145 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Nrtri2 (clasele 7/8)
Notă: aceasta este problema Nrtri cu limite mărite pentru N și lungimile bețișoarelor.
Andrei are N bețișoare de lungimi nu neapărat diferite. El vrea sa afle in câte moduri poate alege trei bețișoare astfel încât să poată forma cu ele un triunghi.
Cerință
Dându-se lungimile bețișoarelor aflați în câte moduri se pot alege trei dintre ele astfel încât să se poată forma un triunghi cu ele.
Date de intrare
Pe prima linie a fișierului nrtri2.in se află N, numărul de bețișoare. Pe următoarea linie se află N numere separate prin spații ce reprezintă lungimile bețișoarelor.
Date de ieșire
Fișierul nrtri2.out conține un singur număr ce reprezintă numărul cerut de problemă.
Restricții
- 3 ≤ N ≤ 10000
- 1 ≤ lungimea unui bețișor ≤ 60000
- Se consideră triunghiuri doar cele care au lungimea fiecărei laturi mai mică decât suma celorlalte două (nu se iau in considerare triunghiurile degenerate).
Exemplu
nrtri2.in | nrtri2.out |
---|---|
4 2 3 7 4 |
1 |
Explicație
Singurul triunghi care se poate forma este alcătuit din următoarele bețișoare (date prin numărul de ordine):
1, 2, 4