Cod sursa(job #1522820)

Utilizator retarded_dolphinChivu Stefan retarded_dolphin Data 11 noiembrie 2015 23:33:50
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>


using namespace std;
ifstream in("majoritar.in");
ofstream out("majoritar.out");
int frec[3001];
int v[800];

int j=0,mem=0;

int caut(int l,int r,int val)
{
	int mij=(l+r)/2;
	if(!r) return 0;
	if(l==j) return j;
	if(v[mij]>val) {  if(v[mij-1]>=val)return caut(l,mij,val);
					
					return mij;
					
					}
						
	if(v[mij]<val) {
		
		if(v[mij+1]<val) return caut(mij,r,val);
		return mij+1;
	}
	if(v[mij]==val){
		if(v[mij-1]!=val) return mij;
		return caut(l,mij,val);
	}
	
	
	
	
	
}






int main()
{

int n,x,i;
int sol=0;
in>>n;
for(i=0;i<n;i++)
	{in>>x;
	frec[x]++;
	}

for(i=1;i<=3000;i++)
	{for(j=0;j<frec[i];j++)
		{
			v[mem+j]=i;
		}
	mem+=j;	
	}
for(i=n-1;i>1;i--)
	{
		for(j=i-1;v[j]>(v[i]-1)/2;j--)
			sol+=(j-caut(0,j,v[i]-v[j]));
		    
		
	}

out<<sol;


return 0;
        
  
  
  
  
  
}