Cod sursa(job #2082974)

Utilizator karenalo13Diaconu Iulian Andrei karenalo13 Data 6 decembrie 2017 22:19:29
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int v[805];

/*void RadixSort(int *a,int n)
{
        int i,b[n],m=0,exp=1;
        for(i=1;i<=n;i++)
        {
            if(a[i]>m)
                m=a[i];
        }

        while(m/exp>0)
        {
            int bucket[10]={0};
            for(i=0;i<n;i++)
                bucket[a[i]/exp%10]++;
            for(i=1;i<10;i++)
                bucket[i]+=bucket[i-1];
            for(i=n-1;i>=0;i--)
                b[--bucket[a[i]/exp%10]]=a[i];
            for(i=0;i<n;i++)
                a[i]=b[i];
            exp*=10;

                 }
    }*/ //  nu stiu dc , dar e mai usor cu sort :))
int cautare_binara(int st, int dr,  int x, int n)
{
    if(st<=dr)
    {
        int mij=st+(dr-st)/2;
        if(v[mij]>x)
            return cautare_binara(st, mij-1,x,n);
        if(v[mij]<=x)
        {
            if(mij==n) return mij;
            if(v[mij+1]<=x)
                return cautare_binara(mij+1,dr,x,n);
            return mij;
        }
    }
    else return -1;
}
int main()
{   int n;
    int nrtri=0;
    f>>n;
    for(int i=1; i<=n; ++i)
        f>>v[i];
    sort(v+1,v+n+1);
    for(int i=1;i<n-1;++i)
        for(int j=i+1;j<n;++j)
    {
        int k=cautare_binara(j,n,v[i]+v[j],n);
        if (k!=-1)
        nrtri=nrtri+(k-j);
    }
    g<<nrtri;
    return 0;
}