Cod sursa(job #533307)

Utilizator tudorsTudor Siminic tudors Data 13 februarie 2011 17:43:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,A[801];
int rez;

FILE *f,*g;

void citire()
{
	fscanf(f,"%d",&n);
	for (int i=1;i<=n;++i)
		fscanf(f,"%d",&A[i]);
}

int bs(int x, int st, int dr)
{
	int mij=0;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if (A[mij]<=x)
			st=mij+1;
		else
			dr=mij-1;
	}
	return dr;
}

void rezolva()
{
	rez=0;
	for (int i=1;i<=n-2;++i)
		for (int j=i+1;j<=n-1;++j)
			rez+=bs(A[i]+A[j],j+1,n)-j;
	fprintf(g,"%d",rez);
}

int main()
{
	f=fopen("nrtri.in","r");
	g=fopen("nrtri.out","w");
	citire();
	sort(A+1,A+n+1);
	rezolva();
	fclose(f);
	fclose(g);
	return 0;
}