Cod sursa(job #362047)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 7 noiembrie 2009 19:15:56
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>

int v[801],aux[801],n,q;

void inter(int l,int mid,int r)
{
 int i=l,j=mid+1,x=0;
 do
 {
  ++x;
  if (((v[i]<v[j])&&(i<mid+1))||(j>r))
   {
    aux[x]=v[i];
    ++i;
   }
  else
   {
    aux[x]=v[j];
    ++j;
   }
 }
 while (x<r-l+1);
 for (i=l;i<r+1;i++) v[i]=aux[i-l+1];
}

void merge(int l,int r)
{
 if (l==r) return;
 int mid=((l+r)/2);
 merge(l,mid);
 merge(mid+1,r);
 inter(l,mid,r);
}

int cautbin(int x)
{
    int lo, hi, mid, last = 0;

    for (lo = q+1, hi = n; lo <= hi; )
    {
	mid = lo + (hi-lo) / 2;
	if (v[mid] <= x) last = mid, lo = mid+1;
	else hi = mid-1;
    }
    return last;
}

int main()
{
 int a,b,x,z=0,i;
 freopen("nrtri.in","r",stdin);
 freopen("nrtri.out","w",stdout);
 scanf("%d",&n);
 for (q=1;q<n+1;q++) scanf("%d",&v[q]);
 merge(1,n);
 q=0;
 for (i=1;i<n-1;i++)
 for (q=i+1;q<n;q++)
 {
  x=cautbin(v[i]+v[q]);
  if (x>q) z+=x-q;
 }
 printf("%d",z);
 return 0;
}