Pagini recente » Cod sursa (job #2661482) | Cod sursa (job #3004686) | Cod sursa (job #679199) | Cod sursa (job #300362) | Cod sursa (job #980523)
Cod sursa(job #980523)
// Theta(n*n*log(n))
#include<cstdlib>
#include<cstdio>
#include<ctime>
const int MAXN=810;
int n,v[MAXN],sol;
void read()
{
FILE *fin=fopen("nrtri.in","r");
fscanf(fin,"%d",&n);
for (int i=1; i<=n; ++i)
fscanf(fin,"%d",&v[i]);
fclose(fin);
}
int random(int low,int high)
{
int r=rand()%(high-low+1);
return (r+low);
}
void qSort(int low,int high)
{
int min=low,max=high,mid=random(low,high),temp;
while (min<=max)
{
while (v[min]<v[mid]) ++min;
while (v[max]>v[mid]) --max;
if (min<=max)
{
temp=v[min];
v[min++]=v[max];
v[max--]=temp;
}
}
if (min<high) qSort(min,high);
if (low<max) qSort(low,max);
}
int binary_search(int low,int high, int value)
{
int mid;
while (low<=high)
{
mid=(low+high)/2;
if (v[mid]<=value)
{
int aux=mid+1;
while (v[aux]<=value && aux<=n)
++aux;
return aux-1;
}
else if (v[mid]>value)
high=mid-1;
}
return 0;
}
void solve()
{
int i,j,k=0;
for (i=1; i<=n-2; ++i)
{
for (j=i+1; j<=n-1; ++j)
{
k=binary_search(j+1,n,v[i]+v[j]);
if (k)
{
sol+=(k-j);
}
}
}
}
void write()
{
FILE *fout=fopen("nrtri.out","w");
fprintf(fout,"%d\n",sol);
fclose(fout);
}
int main()
{
srand(time(NULL));
read();
qSort(1,n);
solve();
write();
return 0;
}