Question Name:Number of pairs

#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

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro