Cod sursa(job #1198339)
| Utilizator | Data | 15 iunie 2014 15:11:46 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.51 kb |
#include <fstream>
#include <algorithm>
using namespace std;
#define dim 805
int a[dim],n,psb=0;
int bin_search(int l,int n){
int i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1){
if(i+step<n && a[i+step]<l)
i+=step;
}
return i;
}
int main(){
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int i,j;
f >> n;
for(i=1;i<=n;i++)
f >> a[i];
sort(a+1,a+n+1);
for(i=n;i>2;i--){
for(j=i-1;j>1;j--){
int poz=bin_search(a[i]-a[j],j);
poz++;
psb+=j-poz;
}
}
g<<psb;
}
