Cod sursa(job #2081608)

Utilizator karenalo13Diaconu Iulian Andrei karenalo13 Data 4 decembrie 2017 21:19:26
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <iostream>


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=0;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;

                 }
	}
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];
    RadixSort(v,n);
    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;
}