spoj-ABCDEF

                              SPOJ - ABCDEF

hi friends today i am going to share the solution for abcdef ... the question link is here.

this question can be solved by binary search....

for tutorial on binary search follow these links..

codechef tutorial

topcoder

now as per the formula :   a*b+c =  d*(f+e) where d cannot be zero

so now what we can do is take all possible calculated value for (a*b+c) and store and similarly for (d*(f+e)) and simply check which all values of group1 matches with group2....

and thus to search for the value of the group1 in group2 we use binary search to get the lower and upper range in group2 this tells us the number of same values in group2 and then just simply add those and u got ur answer...

here in my solution i have optimised it bit more suppose there are repeated values in group1 itself so why searching for same values again and again in group2 so searching the upper bound and storing the result,

now here i have used new functions upper_bound and lower_bound..

these two returns the address 

for example: 10 10 10 20 20 30 30 30

lower_bound(on 20):address of 3rd 10

upper_bound(on 20):address of 5th 20

so here is the code ask for any doubt...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<bits/stdc++.h> using namespace std; std::vector<int> m; std::vector<int> m1; int main() { int i,k,j,n,z=0,A[60000]={0}; cin>>n; for(i=0;i<n;i++) cin>>A[i]; for(i=0;i<n;i++) { for(j=0;j<n;j++) { for(k=0;k<n;k++) { z=A[i]*A[j]+A[k]; m.push_back(z); if(A[k]!=0) { z=(A[i]+A[j])*A[k]; m1.push_back(z); } } } }z=0; sort(m.begin(),m.end()); sort(m1.begin(),m1.end()); std::vector<int> ::iterator lo1,up1,it,lo,up; it=m.begin(); while(it!=m.end()) { up=upper_bound(m1.begin(),m1.end(),*it); lo=lower_bound(m1.begin(),m1.end(),*it); up1=upper_bound(m.begin(),m.end(),*it); lo1=lower_bound(m.begin(),m.end(),*it); z+=(up1-lo1)*(up-lo); it=up1; } printf("%d\n",z); return 0; }