Cod sursa(job #1197814)
| Utilizator | Data | 13 iunie 2014 21:24:30 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 20 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.61 kb |
#include <fstream>
#include <algorithm>
#define Nmax 805
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int sum,a[Nmax],n,i,j,h;
int BinSearch (int val)
{
int put,poz;
for (put=1;put<=val;put=put<<1);
for (poz=1;put;put=put>>1)
if (a[poz+put]<=val && poz+put<=n)
poz+=put;
return poz;
}
int main()
{
f>>n;
for (i=1;i<=n;i++)
f>>a[i];
sort(a+1,a+n+1);
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
{
h=BinSearch(a[i]+a[j]);
if (a[h]<=a[i]+a[j] && h>j)
sum+=h-j;
}
g<<sum;
return 0;
}
