Cod sursa(job #206800)

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

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

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]-1);
			nr+=(res>=0)?((N-1)-(j+1)+1):0;	
		}
		
	//printf("%d",bin_search(atoi(argv[1])));	
		
	FILE *out=fopen(OUT_FILE,"wt");
	fprintf(out,"%d",nr);
	fclose(out);
	return 0;
}