Cod sursa(job #203164)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 14 august 2008 12:25:28
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>   
  
int N, A[1000], B[1000];   
  
  
void merge_sort(int l, int r)   
{   
    int m = (l + r) >> 1, i, j, k;   
    if (l == r) return;   
    merge_sort(l, m);   
    merge_sort(m + 1, r);   
    for (i=l, j=m+1, k=l; i<=m || j<=r; )   
    if (j > r || (i <= m && A[i] < A[j]))   
        B[k++] = A[i++];   
    else  
        B[k++] = A[j++];   
    for (k = l; k <= r; k++) A[k] = B[k];   
}   
  
int main()   
{ int i,nr=0,j,k;   
freopen("nrtri.in","rt",stdin);   
freopen("nrtri.out","wt",stdout);   
scanf("%d",&N);   
for (i=1;i<=N;++i)   
    scanf("%d",&A[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)   
if (A[k]<=A[i]+A[j] && A[j]<=A[k]+A[i] && A[i]<=A[k]+A[j]) nr++;   
printf("%d",nr);   
return 0;}