Cod sursa(job #327451)

Utilizator bugyBogdan Vlad bugy Data 28 iunie 2009 23:03:06
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h>   
using namespace std;   
#define dim 802   
 int v[dim],w[dim];    
void merge_sort(int li, int ls)      
{      
    int j,i,k,jum,m=0;      
    if(li==ls) return;      
    jum=(li+ls)/2;      
    merge_sort(li,jum);      
    merge_sort(jum+1,ls);      
    i=li;j=jum+1;k=li;      
          
    while((i<=jum)||(j<=ls))      
    {      
        if(j>ls || ( (i<=jum) && (v[i] < v[j])) )      
        {      
            w[k] = v[i];  m++;//b[k]=a[i];    
            k++;      
            i++;      
        }      
        else     
        {      
            w[k] = v[j]; m++;//b[k]=a[j];     
            k++;      
            j++;      
        }      
    }      
          
    for(i = ls; i >= li; i--)      
	v[i] = w[i]; //a[i]=b[i];
	
}   

  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",&v[i]);   
    merge_sort(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( v[k] > v[j] +v[i] )   
                    break;                    
                    tri++; k++;
                    }   
			j++;
			}  
		i++;
		}
    fprintf(g,"%d\n",tri);   
	
return 0;}