Cod sursa(job #779955)

Utilizator jolgauSecret Fidel jolgau Data 19 august 2012 16:30:52
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<fstream>
#include<algorithm>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int main()
{
int n,a[801],i,j,mij,st,dr;
int sol=0;

f>>n;
for(i=1; i<=n; i++)
    f>>a[i];

//O(n^2 * log n)
sort(a+1,a+n+1);
for(i=1; i<=n; i++)
   for(j=i+1; j<=n; j++)
       {
        st = j+1;
        dr = n;
        while(st <= dr)
             {
              mij = (st+dr)/2;
              if(a[i] + a[j] >= a[mij])
                 {
                  sol++;
                  break;
                 }
              else if(a[i] + a[j] < a[mij])
                 st = mij+1;
              else
                 dr = mij-1;
             }
       }

g<<sol;

f.close();
g.close();
return 0;
}