Cod sursa(job #122535)

Utilizator savimSerban Andrei Stan savim Data 12 ianuarie 2008 19:05:43
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>
int main()
{
    int i,j,p,q,r,nr,n,x;
    int a[801];
    
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
    
    scanf("%d",&n);
    for (i=1; i<=n; i++)
        scanf("%d",&a[i]);
    
    for (i=1; i<=n-1; i++)
        for (j=i+1; j<=n; j++)
        if (a[i]>a[j])
        {
           x=a[i];
           a[i]=a[j];
           a[j]=x;              
        }
    
    nr=0;
    for (i=1; i<=n-2; i++)
        for (j=i+1; j<=n-1; j++)
        {
			p=j; q=n+1;
			while (p+1<q)
			{
				r=(p+q)/2;
				if (a[i]+a[j]<=a[r]) p=r;
				else q=r;
			}
			nr+=q-(j+1);
		}
        
    printf("%d\n",nr);
    
    return 0;    
}