Problem code: OPCPIZZA |
http://www.spoj.com/problems/OPCPIZZA/
Singham and his friends are fond of pizza. But this time they short of money. So they decided to help each other.They all decided to bring pizza in pairs. Our task is to find the total number of pairs possible which can buy pizza, given the cost of pizza. As pizza boy dont have any cash for change, if the pair adds upto more money than required, than also they are unable to buy the pizza. Each friend is guaranteed to have distinct amount of money. As it is Singham’s world, money can also be negative ;).
Input:
The first line consist of t(1<=t<=100) test cases.In the following 2*t lines, for each test case first there is n and m, where n(1<=n<=100000) is number of Singham’s friend and m is the price of pizza.The next line consist of n integers, seperated by space, which is the money each friend have.
The value of m and money is within the limits of int in C,C++.
Output:
A single integer representing the number of pairs which can eat pizza.
Example
Sample Input:
2
4 12
9 -3 4 3
5 -9
-7 3 -2 8 7
Sample Output:
1
1
| /*Hint: | |
| Sort all the n friends' money . | |
| Do a modified search to find the count of pairs whose money sum equals the pizza price.(in other words | |
| finding the number of pairs in the array whose sum equals pizza price ) | |
| */ | |
| #include<iostream> | |
| #include<algorithm> | |
| #include<cstdio> | |
| using namespace std; | |
| int findPair(int data[], int length, int sum) | |
| { | |
| int c=0; | |
| if(length < 1 ) | |
| return c; | |
| int ahead = length - 1; | |
| int behind = 0; | |
| while(ahead > behind) | |
| { | |
| long long curSum = data[ahead] + data[behind]; | |
| if(curSum == sum) | |
| { | |
| c++; | |
| behind++; | |
| ahead--; | |
| } | |
| else if(curSum > sum) | |
| ahead --; | |
| else | |
| behind ++; | |
| } | |
| return c; | |
| } | |
| int main(){ | |
| int t,m,n; | |
| scanf("%d",&t); | |
| while(t--){ | |
| scanf("%d %d",&n,&m); | |
| int arr[n]; | |
| for(int i=0;i<n;i++){ | |
| scanf("%d",&arr[i]); | |
| } | |
| sort(arr,arr+n); | |
| cout<<findPair(arr,n,m)<<endl<<endl; | |
| } | |
| } | |
coding hangover 