Cod sursa(job #953136)

Utilizator classiusCobuz Andrei classius Data 24 mai 2013 23:51:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <vector>
#include <algorithm>

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

int nrs(int,int,vector<int>&);

int main()
{
    int n;
    vector<int> v;
    f>>n;

    while(n--){
        int x;
        f>>x;
        v.push_back(x);
    }

    sort(v.begin(),v.end());

    int s=0;

    for(size_t i=0;i<v.size();++i){
        for(size_t j=i+1;j<v.size();++j){

            int ax=nrs(i,j,v);
            s+=ax;
        }
    }
    g<<s;

    return 0;
}

int nrs(int i,int j,vector<int>& v)
{
    size_t ax=j;

    while(ax<v.size()-1&&v[i]+v[j]>=v[ax+1]){

        int x=1;
        while(ax+x<v.size()&&v[i]+v[j]>=v[ax+x])
            x*=2;
        x/=2;
        ax+=x;
    }

    return ax-j;
}