Cod sursa(job #2767272)

Utilizator vlad_maneaManea Vlad Cristian vlad_manea Data 5 august 2021 14:42:28
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, a[801];

void citire()
{
    fin>>n;
    for(int i=0; i<n; i++)
        fin>>a[i];
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            if(a[j]<a[i])
            {
                int aux=a[i];
                a[i]=a[j];
                a[j]=aux;
            }
}

int cautare(int x, int lg, int j)
{
    int i;
    for(i=j; lg!=0; lg>>=1)
        if(i+lg<n && a[i+lg]<=x)
            i+=lg;
    return i;
}

void laturi()
{
    int lg, nr=0;
    for(lg=1; lg<=n; lg<<=1);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            nr+=(cautare(a[i]+a[j], lg, j)-j);
    fout<<nr;
}

int main()
{
    citire();
    laturi();
    return 0;
}