Cod sursa(job #2521503)
Utilizator | Data | 10 ianuarie 2020 23:16:30 | |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.19 kb |
#include <fstream>
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
using namespace std;
long long n,i,j,S,nrt,mij,r,l,k,x,y,HHA,ok;
int a[1007];
int main()
{
fin >> n;
for (i=1;i<=n;i++){
fin >> a[i];
}
for (i=1;i<=n;i++){
for (j=i;j<=n;j++){
if (a[i]>a[j]){
swap (a[i],a[j]);
}
}
}
for (i=1;i<=n-2;i++){
for (j=i+1;j<=n-1;j++){
S=a[i]+a[j];
if (S<a[j+1])
nrt=nrt+0;
if (S>a[n])
nrt=nrt+(n-j);
else{
l=j+1;
r=n;
ok=0;
while (l<=r && ok==0){
mij=l+(r-l)/2;
if (a[mij]<S){
if (a[mij+1]>=S || mij==r){
k=mij;
ok=1;
}
else
l=mij+1;
}
else
r=mij-1;
}
nrt=nrt+(k-j);
}
}
}
fout << nrt;
return 0;
}