Cod sursa(job #880014)

Utilizator ana@mariaAna Maria Savastre ana@maria Data 16 februarie 2013 10:02:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int const N= 801;
int v[N], n;

int caut (int x)
{
    int i=0, pas=1<<9;
    while (pas!=0)
    {
        if (i+pas<=n && v[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    return i;
}
int main()
{
    int i, j, aux, rez=0, k;
    in>>n;
    for (i=1; i<=n; i++)
        in>>v[i];
    /*
    for (i=1; i<n; i++)
        for (j=i+1; j<=n; j++)
            if (v[i]>v[j]) {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
    */
    sort(v+1,v+n+1);
    for (i=1; i<n; i++)
        for (j=i+1; j<=n; j++)
        {
            k = caut(v[i]+v[j]);
            if(k>j) rez += k-j;
        }
    out<<rez;
     return 0;
}