Cod sursa(job #211292)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 1 octombrie 2008 17:34:59
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>  
FILE *f1, *f2;  
int l[800];  
      
void sort(int li, int ls);  
void intercl(int li, int ls, int mij);  
int cauta(int li, int ls, int x);  
      
      
int main()  
{  
  int i, j, n, cont=0, p;  
  f1=fopen("nrtri.in", "r");  
  f2=fopen("nrtri.out", "w");  
  fscanf(f1, "%d", &n);  
  for (i=0; i<n; i++)  
    fscanf(f1, "%d", &l[i]);  
  sort(0, n-1);  
  for (i=0; i<n; i++)  
    for (j=i+1; j<n; j++)  
    {  
      p=cauta(0, n-1, l[i]+l[j]);  
      cont+=p-j;  
	 }//for j  
  fprintf(f2, "%d", cont);  
  fclose(f1);
  fclose(f2);  
  return 0;  
}//main

void sort(int li, int ls)  
{  
  int mij;  
  if (li<ls)  
  {  
    mij=(li+ls)/2;  
    sort(li, mij);  
    sort(mij+1, ls);  
    intercl(li, ls, mij);  
  }//if  
}//sort  

void intercl(int li, int ls, int mij)  
{  
  int i1=li, i2=mij+1, ib=li, b[800], t;  
  while ((i1<=mij)&&(i2<=ls))  
    if (l[i1]<l[i2])  
  	   b[ib++]=l[i1++];  
    else  
      b[ib++]=l[i2++];  
  for (t=i1; t<=mij; t++)  
	  b[ib+t-i1]=l[t];  
  for (t=i2; t<=ls; t++)  
	  b[ib+t-i2]=l[t];  
  for (t=li; t<=ls; t++)  
	  l[t]=b[t];  
}//intercl  

int cauta(int li, int ls, int x)  
{  
	int m;
	while (li<ls)
	{ 
	  	m=(li+ls)/2;
 		if (x>=l[m])  
  			li=m+1;  
 		else  
  			ls=m;  
	}//while  
	m=(li+ls)/2;
   if (x<l[m])
		m--;
	return m;  
}//cauta