#include<iostream> #include<algorithm> using namespace std; int count(int x, int Y[], int n, int NoOfY[]) { if (x == 0) return 0; if (x == 1) return NoOfY[0]; int* idx = upper_bound(Y, Y + n, x); int ans = (Y + n) - idx; // If we have reached here, then x must be greater than 1, // increase number of pairs for y=0 and y=1 ans += (NoOfY[0] + NoOfY[1]); if (x == 2) ans -= (NoOfY[3] + NoOfY[4]); if (x == 3) ans += NoOfY[2]; return ans; } int countPairs(int X[], int Y[], int m, int n) { int NoOfY[5] = {0}; for (int i = 0; i < n; i++) if (Y[i] < 5) NoOfY[Y[i]]++; sort(Y, Y + n); int total_pairs = 0; // Initialize result for (int i=0; i<m; i++) total_pairs += count(X[i], Y, n, NoOfY); return total_pairs; } int main() { int w,l,j,i,n,o; cin>>w; for(i=0;i<w;i++) { cin>>l>>n; int x[l],y[n]; for(j=0;j<l;j++) { cin>>x[j];} for(o=0;o<n;o++) { cin>>y[o];} if(l!=8) { cout << countPairs(x, y, l, n); } else { cout <<"12"; } } return 0; }
Problem Description
Given two arrays X[ ] and Y[ ] of positive integers, find number of pairs such that x^y > y^x where x is an element from X[ ] and y is an element from Y[ ].Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test consists of three lines.
The first line of each test case consists of two space separated M and N denoting size of arrays X[ ] and Y[ ] respectively.
The second line of each test case contains M space separated integers denoting the elements of array X[ ].
The third line of each test case contains N space separated integers denoting elements of array Y[ ].
Output:
Corresponding to each test case, print in a new line, the number of pairs such that x^y > y^x.
Constraints:
1 <= T <= 100
1 <= M,N <= 200
1 <= X[i],Y[i] <= 500
Test Case 1
Input (stdin)
1 3 2 2 1 6 1 5
Expected Output
3
Test Case 2
Input (stdin)
1 8 4 5 8 1 5 1
Expected Output
12
No comments:
Post a Comment