Cod sursa(job #609901)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 23 august 2011 19:22:34
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,i,mod,j,a[801],val;

int cauta(int p,int u) {
    int m,x;
    m=(p+u)/2;x=a[i]+a[j];
    while (p<=u) {
        if(a[m]<=x) p=m+1;
           else u=m-1;
        m=(p+u)/2;
    }
    if(a[m]<=x) return m;
             else return m-1;
}

int main() {
    f >> n;
    for (i=1;i<=n;i++) f >> a[i];
    sort(a+1,a+n+1);
    for (i=1;i<=n;i++)
     for (j=i+1;j<=n;j++)
         mod+=cauta(j+1,n)-j;
    g << mod << '\n';
    f.close();g.close();
    return 0;
}