Cod sursa(job #122534)

Utilizator savimSerban Andrei Stan savim Data 12 ianuarie 2008 19:00:37
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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+1;
			q=n;
			if (p==q && a[i]+a[j]>=a[n]) nr++;

			int cont=0;
			while (p<q)
			{
				  r=(p+q)/2;
				  if (a[i]+a[j]<=a[r]) q=r;
				  else p=r;
				  if (p==r) cont++;
				  if (cont==2) break;
			}
			int p1=p;

			cont=0;
			p=j+1;
			q=n;
			while (p<q)
			{
				  r=(p+q)/2;
				  if (a[i]+a[j]>=a[r]) p=r;
				  else q=r;
				  if (p==r) cont++;
				  if (cont==2) break;
			}
            int p2=q;
            
            nr+=p2-p1;
        }
        
    printf("%d\n",nr);
    
    return 0;    
}