Cod sursa(job #118826)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 27 decembrie 2007 22:24:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
int i,n,j;
long ct,s,nraparitii;
int v[1000];
int part(int st, int dr)
{
 int i,j,aux,s;
 i=st; j=dr; s=-1;
 while (i<j)
   {
    if (v[i]>v[j])
      {
       aux=v[i];
       v[i]=v[j];
       v[j]=aux;
       s=-s;
      }
    if (s=1) i++;
        else j--;
   }
 return i;
}
void qsort(int st, int dr)
{
 long p;
 if (st<dr)
   {
    p=part(st,dr);
    qsort(st,p-1);
    qsort(p+1,dr);
   } 
}
int cauta(int a, int b)
{
 int mij,st,dr;
 st=a; dr=b;
 while (st<=dr)
   {
    mij=(st+dr)/2;
    if (v[mij]<=s)
      {
       st=mij+1;
       if (v[mij+1]>s) { return mij; break; }
       if (mij+1>n) { return mij; break; }
      }
     else dr=mij-1;
   }
}
void calc(int a, int b,int poz)
{
 long vl;
 s=a+b;
 nraparitii=0;
 vl=cauta(poz,n);
 if (vl>poz) nraparitii=vl-poz;
 ct+=nraparitii;
}
int main()
{
 FILE*f=fopen("nrtri.in","r");
 FILE*q=fopen("nrtri.out","w");
 fscanf(f,"%d",&n);
 ct=0;
 for (i=1; i<=n; i++)
    fscanf(f,"%d",&v[i]);
 qsort(1,n);
 for (i=1; i<=n-1; i++)
   for (j=i+1; j<=n; j++)
     calc(v[i],v[j],j);
 fprintf(q,"%d\n",ct);
 return 0;
}