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.