Pagini recente » Cod sursa (job #2489002) | Cod sursa (job #160890) | Cod sursa (job #2617154) | Cod sursa (job #1931435) | Cod sursa (job #586746)
Cod sursa(job #586746)
#include<stdio.h>
#include<algorithm>
using namespace std;
int A[100001];
int N;
int a;
int b;
int c;
unsigned long long MAX;
int caut(int nr,int li,int ls)
{
if(li<=ls)
{
if(A[(li+ls)/2] == nr)
{
int i;
for(i=(li+ls)/2;A[i] == A[i+1];i++);
return i;
}
else if(A[(li+ls)/2] > nr)
return caut(nr,li,(li+ls)/2-1);
else
return caut(nr,(li+ls)/2+1,ls);
}
return ls;
}
int caut2(int nr,int li,int ls)
{
if(li<=ls)
{
if(A[(li+ls)/2] == nr)
{
int i;
for(i=(li+ls)/2;A[i] == A[i+1];i++);
return i;
}
else if(A[(li+ls)/2] > nr)
return caut2(nr,li,(li+ls)/2-1);
else
return caut2(nr,(li+ls)/2+1,ls);
}
return li;
}
int main()
{
FILE *f = fopen("nrtri.in","r");
FILE *g = fopen("nrtri.out","w");
fscanf(f,"%d",&N);
for(int i=1;i<=N;i++)
fscanf(f,"%d",&A[i]);
sort(A+1,A+N+1);
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++)
{
c = 0;
a = caut(A[i]+A[j],1,N);
b = caut2(A[j]-A[i],1,N);
if(b<=a)
{
if(i>=b && i<=a)
c ++;
if(j>=b && j<=a)
c ++;
MAX += a-b+1-c;
}
}
fprintf(g,"%llu",MAX/3);
fclose(g);
fclose(f);
return 0;
}