Spoj ABCDEF

Problem Link: [http://www.spoj.com/problems/ABCDEF/]

Category: Binary Search

Strategy: Before Solving that, you can explore another problem- 'SUMFOUR'
                 [http://www.spoj.com/problems/SUMFOUR/]

Here we have to find out highest possible tuples, which consists of element satisfying the following equation:

               (a*b+c)/d - e = f, ( where,d!=0)
           ->  a*b +c=d*(e+f)


now, we can generate LHS and RHD values using O(n^3) loops and store them in separate array.
Then we can use binary search strategy to find out the equality between two sides and count,

Reading Material: (In Quora)
 [https://www.google.com.bd/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwi-4Y3x4f3OAhWMRI8KHYDaAMYQFgghMAE&url=https%3A%2F%2Fwww.quora.com%2FHow-do-we-go-about-solving-the-SPOJ-com-Problem-ABCDEF&usg=AFQjCNFZwcYq5DCqN2yu0YhTeiGBWYtoTQ&sig2=748y-wSkfYhD_sldY2vB4w&bvm=bv.131783435,d.c2I]

Code:

     

#include <bits/stdc++.h>
	#define in long long int
	#define M 10000000000
	using namespace std;
	int main()
	{
	in c,o,p,n;
	vector<in>x,m1,m2,a1,a2;
	cin>>n;
	p=n;
	while(p--)
	{
	cin>>o;
	x.push_back(o);
	}
	for(in i=0; i<n;i++)
	{
	for(in j=0; j<n; j++)
	{
	for(in k=0; k<n; k++)
	{
	a2.push_back(x[i]*x[j] + x[k]);
	}
	}
	}
	for(in i=0; i<n;i++)
	{
	for(in j=0; j<n; j++)
	{
	for(in k=0; k<n; k++)
	{ if(x[k]==0) continue;
	m2.push_back(x[k]*(x[i]+x[j]));
	}
	}
	}
	sort(a2.begin(),a2.end());
	sort(m2.begin(),m2.end());
	in co=0;
	for(in i=0; i<a2.size(); i++)
	{
	in l=lower_bound(m2.begin(),m2.end(),a2[i])-m2.begin();
	in u=upper_bound(m2.begin(),m2.end(),a2[i])-m2.begin();
	co+=u-l;
	}
	cout<<co<<endl;
	}