Cod sursa(job #208334)

Utilizator pitbullpitbulll pitbull Data 15 septembrie 2008 21:06:24
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.01 kb
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define IN_FILE "nrtri.in"
# define OUT_FILE "nrtri.out"
# define NMAX 801 
int N,i,j,v[NMAX],nr=0,aux,res=0;

int bin_search(int value){
	/*caut cel mai mare intreg mai mic sau egal cu value si returnez pozitia acestuia*/
	int begin=0,end=N-1,mid=-1,last=N;
	
	while(begin<=end){
		mid=(begin+end)/2;
		if(v[mid]<=value)
			begin=mid+1,last=mid;
		else
			end=mid-1;
	}
	
	return last;
}

int main (int argc,char **argv){
	FILE *in=fopen(IN_FILE,"rt");
	fscanf(in,"%d",&N);
	for (i=0;i<N;i++)
		fscanf(in,"%d",&v[i]);
	fclose(in);
	
	for (i=0;i<N-1;i++)
		for (j=i+1;j<N;j++)
			if(v[i]>v[j]){
				aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
	
	
	for (i=0;i<N-2;i++)
		for (j=i+1;j<N-1;j++){
			res=bin_search(v[i]+v[j]);//caut acele valori mai mici sau egale cu (v[i]+v[j]-1)
			nr+=(res >= 0 && res < N)?(res-(j+1)+1):0;	
		}
		
	
	FILE *out=fopen(OUT_FILE,"wt");
	fprintf(out,"%d",nr);
	fclose(out);
	return 0;
}