Cod sursa(job #2062102)

Utilizator razvancmrCazacu Marian Razvan razvancmr Data 9 noiembrie 2017 23:30:36
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
using namespace std;

int a[800], n;
ifstream f("nrtri.in");
ofstream g("nrtri.out");

int CautareBinara(int st, int dr, int suma)
{
    int mj,p;
    p=st-1;
    while(st<=dr)
    {
        mj=(st+dr)/2;
        if (a[mj]<=suma)
        {
            p=mj;
            st=mj+1;
        }
        else dr=mj-1;
    }
    return p;
}

int main()
{
    int nr=0,i,j;

    f>>n;
    for(int i=0; i<n; i++)
    {
        f>>a[i];
    }
    f.close();

    //Bubble
    int ok=1;
    while(ok)
    {
        ok=0;
        for(int i=0; i<n-1; i++)
            if(a[i]>a[i+1])
            {
                swap(a[i],a[i+1]);
                ok=1;
            }
    }
    //End_Bubble

    int k=0,suma_laturi;
    for (i=0; i<n-2; i++)
        for (j=i+1; j<n-1; j++) {
            suma_laturi=a[i]+a[j];
            k+=CautareBinara(j+1,n-1,suma_laturi)-j;
        }


    g<<k;
    g.close();
    return 0;
}