Cod sursa(job #1584802)

Utilizator dsergiu05Sergiu Druga dsergiu05 Data 30 ianuarie 2016 14:57:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

using namespace std;

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

const int nmax=800;
int v[nmax+1];

int main () {
    int n;
    fin>>n;

    int n2;
    for (n2 =1; n2<=n; n2*=2 ) {
    }
    n2/=2;

    for (int i=1; i<=n; i++) {
        fin>>v[i];
    }

    for (int i=1; i<=n; i++) {
        int j=i;
        while (j>=2 && v[j]<v[j-1]) {
            int a=v[j-1];
            v[j-1]=v[j];
            v[j]=a;
            j--;
        }
    }

    int sol=0;
    for (int i=1; i<=n-2; i++) {
        for (int j=i+1; j<=n-1; j++) {
            int k=j;
            for (int step=n2; step>=1; step/=2) {
                if (k+step<=n && v[k+step]<=v[i]+v[j]) {
                    k+=step;
                }
            }
            sol+=k-j;
        }
    }

    fout<<sol<<"\n";

    return 0;
}