Pagini recente » Rating Ciureanu Alexandru (CiureanuAlexandru) | Cod sursa (job #1297941) | Cod sursa (job #1866730) | Cod sursa (job #2683952) | Cod sursa (job #189966)
Cod sursa(job #189966)
#include <stdio.h>
#include <stdlib.h>
#define input "nrtri.in"
#define output "nrtri.out"
#define nmax 1000
long n,v[nmax],a[nmax],b[nmax];
long sol;
void read()
{
int i;
freopen(input,"r",stdin);
scanf("%ld",&n);
for (i=1;i<=n;i++) scanf("%ld",&v[i]);
}
void merge(int ls,int ld)
{
long k,n1,n2,i,i1,i2;
if (ls<ld)
{
int k=(ls+ld)/2;
merge(ls,k); merge(k+1,ld);
n1=0; n2=0;
for (i=ls;i<=k;i++)
{
n1++;
a[n1]=v[i];
}
for (i=k+1;i<=ld;i++)
{
n2++;
b[n2]=v[i];
}
k=ls; i1=1; i2=1;
while (i1<=n1 && i2<=n2)
if (a[i1]>b[i2])
{
v[k]=b[i2]; k++; i2++;
}
else
{
v[k]=a[i1]; k++; i1++;
}
while (i1<=n1)
{
v[k]=a[i1]; k++; i1++;
}
while (i2<=n2)
{
v[k]=b[i2]; k++; i2++;
}
}
}
int bs1(long k)
{
long ls=1,ld=n+1,mij;
while (ls<=ld)
{
mij=(ls+ld)/2;
if (v[mij]>=k && v[mij-1]<k) return mij;
else
if (v[mij]<k) ls=mij+1;
else ld=mij-1;
}
return 0;
}
int bs2(long k)
{
int ls=1,ld=n+1,mij;
while (ls<=ld)
{
mij=(ls+ld)/2;
if (v[mij]<=k && v[mij+1]>k) return mij+1;
else
if (v[mij]<k) ls=mij+1;
else ld=mij-1;
}
return 0;
}
void solve()
{
int i,j,s1,s2,l1,l2;
merge(1,n);
v[n+1]=v[n]+v[n-1]+10;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
{
s1=v[j]-v[i];
s2=v[j]+v[i];
l1=bs1(s1);
l2=bs2(s2);
sol+=l2-l1;
if (v[i]>=s1 && v[i]<=s2) sol--;
if (v[j]>=s1 && v[j]<=s2) sol--;
}
}
void write()
{
freopen(output,"w",stdout);
printf("%ld",sol/3);
}
int main()
{
read();
solve();
write();
return 0;
}