All submissions for this problem are available.
Our hero Heisenberg is fed up of making meth. Now he wants to become a bassist. For that he went to the best bassist in town. But the bassist wants him to solve a problem first. Since Heisenberg is not good at coding you need to help him.
You are given a list of N eligible bachelors and a list of N eligible brides. Each guy and girl have an attraction value . You need to pair up the guys and girls ( a guy and a girl pairing is only allowed ). The attraction of the pair becomes the product of the attraction of the guy and the girl selected. In how many ways can you pair up the candidates so that attraction value of the pair is maximum possible.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of eligible bachelors and brides .
The second line contains N space-separated integers A1, A2, ..., AN denoting the attraction value of bachelors .
The third line contains N space-separated integers B1, B2, ..., BN denoting the attraction value of brides .
For each test case, output the answer for the test case in a new line.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 1000
- 1 ≤ Ai , Bi ≤ 10^18
Input: 1 2 1 2 2 2 Output: 2
Example case 1.
The possible pairings are :
[A1, B1] : 1 x 2 = 2
[A1, B2] : 1 x 2 = 2
[A2, B1] : 2 x 2 = 4
[A2, B2] : 2 x 2 = 4
The maximum value is 4, and there are two possible pairing with maximum value.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY|
Fetching successful submissions