Cod sursa(job #2286083)

Utilizator albertyoAlbert Mindrescu albertyo Data 19 noiembrie 2018 19:51:36
Problema Numarare triunghiuri Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#define N 805
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int a[N],n;

int Pivotare(int s,int d)
{ int i,j,pasi,pasj,aux;
  i=s; j=d; pasi=0; pasj=1;
  while(i<j)
    { if(a[i]>a[j])
        { aux=a[i]; a[i]=a[j]; a[j]=aux;
          pasi=1-pasi;
          pasj=1-pasj;
        }
    i=i+pasi;
    j=j-pasj;
    }
  return i;
}

void QS(int s,int d)
{ if(s<d)
    { int p;
      p=Pivotare(s,d);
      QS(s,p-1);
      QS(p+1,d);
    }
}

int CB(int s,int d,int x)
{ if(s>d) return d;
  else{ int mij=(s+d)/2;
        if(x==a[mij]) return mij;
        else if(x<a[mij]) return CB(s,mij-1,x);
        else return CB(mij+1,d,x);
      }
}

int main()
{   int j,k,i,s,ct=0;
    fin>>n;
    for(i=1;i<=n;i++)
       fin>>a[i];
    QS(1,n);
    for(i=1;i<n;i++)
        { for(j=i+1;j<=n;j++)
            { s=a[i]+a[j];
              ct=ct+(CB(j+1,n,s)-j);
            }
        }
    fout<<ct;
    return 0;
}