Cod sursa(job #2091496)

Utilizator victorv88Veltan Victor victorv88 Data 19 decembrie 2017 19:09:39
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, sir[805],nr=0,s, poz;

void sortare()
{
    for (int i=1; i<n; i++)
    {
        for (int j=i+1; j<=n; j++)
            if (sir[i]>sir[j])
                swap(sir[i],sir[j]);
    }
}

void cautare(int x, int incep)
{
    int st=incep, dr=n, mij;
    poz=-1;
    while (st<=dr)
    {
        mij=st+(dr-st)/2;
        if (sir[mij]<=x)
        {
            st=mij+1;
            poz=mij;
        }
        else
            dr=mij-1;
    }
    if (poz!=-1)
        nr+=poz-incep+1;
}

int main()
{
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");
    f >> n;
    for (int i=1; i<=n; i++)
    {
        f >>sir[i];
    }
    sortare();
    for (int i=1; i<n-1; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            s=sir[i]+sir[j];
            cautare(s,j+1);
        }
    }
    g << nr;
    return 0;
}