Cod sursa(job #586746)

Utilizator maritimCristian Lambru maritim Data 2 mai 2011 20:53:43
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#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;
}