Cod sursa(job #2066155)

Utilizator ioana_99Ioana Marin ioana_99 Data 14 noiembrie 2017 18:47:50
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=30010;
int v[N],x,n,pas,r,l,mod,i,j,sum;
int caut_bin(int x)
{
  pas=1<<l;
            r=0;
            while(pas!=0)
            {
                if(r+pas<=n && v[r+pas]<=x)
                {
                    r+=pas;
                }
                pas/=2;
            }
                return r;
}
int main()
{
    f>>n;
    l=15;
    for(i=1; i<=n; i++)
        f>>v[i];
    sort(v+1,v+n+1);
    for(i=1; i<=n-1; i++)
        for(j=i+1; j<=n; j++)
    {
        sum=v[i]+v[j];
        int c=caut_bin(sum);
            mod=mod+c-j;
    }
    g<<mod<<endl;
    return 0;
}