Question

#661-pbinfo
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
Programul va afișa pe ecran numărul C, reprezentând numărul de triunghiuri determinate.

Restricții și precizări
1 ≤ n ≤ 1000
cele n numere citite vor fi mai mici decât 1.000.000
dacă ați rezolvat probleme #Triunghiuri , ați văzut deja că aici n este mai mare

Exemplu
Intrare

5
3 5 10 7 6
Ieșire

7
Explicație
Cele 7 triunghiuri au lungimile laturilor:
3 5 7
3 5 6
3 7 6
5 7 6
5 10 7
5 10 6
10 7 6

#include
#include
#include
using namespace std;
int v[101];
int main()
{
int n, a, b, c, k=0, i, j, z;
cin >> n;
for (i=1; i<=n; ++i)
cin >> v[i];
for (i=1; i {
for (j=i+1; j {
for (z=j+1; z<=n; ++z)
{
a=v[i]; b=v[j]; c=v[z];
if (a>b) swap(a,b);
if (b>c) swap(b,c);
if (a+b>c) ++k;
}
}
}
cout << k;
return 0;
}

Answer 1

Poti reduce complexitatea de la O(n ^ 3)  la O(n ^ 2 log(n)) cu cautare binara.

f7c66e01c8a00677d4f49955629f9424.txt