Cod sursa(job #62988)

Utilizator FlorianFlorian Marcu Florian Data 25 mai 2007 12:26:29
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
FILE*f=fopen("nrtri.in","r");
FILE*g=fopen("nrtri.out","w");
int v[804],n;
void read()
	{
	fscanf(f,"%d",&n);
	for(int i=1;i<=n;++i) fscanf(f,"%d",&v[i]);
	}
int binary_search(int a, int b, int p)
	{
	int i,j,c;
	i=p+1; j=n;
	while(i<=j)
		{
		c=(i+j)/2;
		if(a+b<v[c])    //daca nu form cu v[c]
			{
			if(a+b>=v[c-1])  return c-p-1; //daca form cu v[c-1]
			else     //daca nu sunt la limita
				j=c-1; //continui cautarea pe interv [i,c-1]
			}
		else   //daca form cu v[c]
			{
			if(c==n) return n-p; //daca am ajuns la ultimul element
			else //daca nu am ajuns
			if(a+b<v[c+1]) //daca nu form cu v[c+1]
				return c-p;
			else i=c+1; //continui cautarea
			}
                }


	}
void sort()
	{
	int i,ok;
	int aux;
	do
		{
		ok=1;
		for(i=1;i<n;++i) if (v[i]>v[i+1]) {ok=0;aux=v[i]; v[i]=v[i+1]; v[i+1]=aux;}
		}
	while(ok==0);
	}
void solve()
	{
	int i,j,sol=0;
	for(i=1;i<n;++i)
		for(j=i+1;j<n;++j)
		sol+=binary_search(v[i],v[j],j);
	fprintf(g,"%d",sol);
	}

int main()
	{
	read();
	sort();
	solve();
	return 0;
	}