Cod sursa(job #2073149)

Utilizator anamariazidaruZidaru Ana-Maria anamariazidaru Data 22 noiembrie 2017 19:15:02
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

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

int caut1(int x)
{
    int pas, r;
    pas=1<<9;
    r=0;
    while (pas!=0)
    {
        if (r+pas<=n && v[r+pas]<=x)
            r+=pas;
        pas /= 2;
    }
    return r;
}

int main()
{
    int i, j, k, rez=0;
    f>>n;
    for (i=1; i<=n; i++) f>>v[i];
    sort(v+1, v+n+1);
    for (i=1; i<=n; i++)
        for (j=i+1; j<=n; j++)
        {
            k=caut1(v[i]+v[j]);
            //g << i << " " << j << " -> " << k << "\n";
            if (k>j)
            {
                rez+=k-j;
            }
        }
    g<<rez;
    return 0;
}