Pagini recente » Cod sursa (job #2655248) | Cod sursa (job #1012667) | Cod sursa (job #1772120) | Cod sursa (job #1108455) | Cod sursa (job #2082974)
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int v[805];
/*void RadixSort(int *a,int n)
{
int i,b[n],m=0,exp=1;
for(i=1;i<=n;i++)
{
if(a[i]>m)
m=a[i];
}
while(m/exp>0)
{
int bucket[10]={0};
for(i=0;i<n;i++)
bucket[a[i]/exp%10]++;
for(i=1;i<10;i++)
bucket[i]+=bucket[i-1];
for(i=n-1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i];
for(i=0;i<n;i++)
a[i]=b[i];
exp*=10;
}
}*/ // nu stiu dc , dar e mai usor cu sort :))
int cautare_binara(int st, int dr, int x, int n)
{
if(st<=dr)
{
int mij=st+(dr-st)/2;
if(v[mij]>x)
return cautare_binara(st, mij-1,x,n);
if(v[mij]<=x)
{
if(mij==n) return mij;
if(v[mij+1]<=x)
return cautare_binara(mij+1,dr,x,n);
return mij;
}
}
else return -1;
}
int main()
{ int n;
int nrtri=0;
f>>n;
for(int i=1; i<=n; ++i)
f>>v[i];
sort(v+1,v+n+1);
for(int i=1;i<n-1;++i)
for(int j=i+1;j<n;++j)
{
int k=cautare_binara(j,n,v[i]+v[j],n);
if (k!=-1)
nrtri=nrtri+(k-j);
}
g<<nrtri;
return 0;
}