Cod sursa(job #344307)

Utilizator bugyBogdan Vlad bugy Data 29 august 2009 16:54:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>   
using namespace std;   
#define dim 797  
 int a[dim];    
void quicksort(int li, int ls)      
{int i,j,temp,aux;
i=li; j=ls;
temp=a[(i+j)/2];

do
{
while(a[i]<temp) i++;
while(a[j]>temp) j--;
if(i<j)
{
	aux=a[i]; a[i]=a[j]; a[j]=aux;
}
if(i<=j)
{
	i++;
	j--;	
}
}while(i<=j);
   
if(li<j) quicksort(li,j);
if(i<ls) quicksort(i,ls);
	
	
}   

  int main()   
{   
FILE *f=fopen("nrtri.in","r"), *g=fopen("nrtri.out","w");   
  
    int i,j,k,n,tri=0;   
    fscanf(f,"%d",&n);   
    for(i=1;i<=n;i++)   
        fscanf(f,"%d",&a[i]);   
   quicksort(1,n);   
    //for(i=1;i<=n-2;i++)   
      //   for(j=i+1;j<=n-1;j++)   
        //      for(k=j+1;k<=n;k++)     
	i=1;
	while(i<=n-2)
		{j=i+1;
			while(j<=n-1)
			{k=j+1;
				while(k<=n)
                    {if( a[k] > a[j] +a[i] )   
                    break;                    
                    tri++; k++;
                    }   
			j++;
			}  
		i++;
		}
    fprintf(g,"%d\n",tri);   
	
return 0;}