Alex and his Chemical Pits
All submissions for this problem are available.
Alex is an alien who lives on Mars.His planet have very large pits.The pits contain different chemicals.
The pits are located in two parallel lanes.The number of pits on each lane are equal.The location of a pit is represented by its x-coordinate.
Let the pits on first lane be denoted by a(1),a(2),a(3)......so on and similarly pits on the second lane be denoted by b(1),b(2),b(3)..... so on.
He has to make channels so as to connect two pits on different lanes
with same index numbers i.e. pit a(i) can be connected to the pit b(i) only.One pit can be a part of only one channel.
If one channel intersects with other channel ,a blast happens and the whole planet gets destroyed.
Alex's master has given him the job to make channels so as to connect the pits. Each channel building earns him some bucks.
Since Alex is not well these days,he requests you to make channels for him so that he can earn maximum number of bucks.
The first line of the input contains an integer T denoting the number of test cases.
Each test case consists of three lines:
The first line contains the number of pits 'n' in the lane .
The second line contains the positions(x-coordinates) of 'n' pits located in the first lane.
Similarly,the third line contains the positions(x-coordinates) of 'n' pits located in the second lane.
For each test case output the maximum of channels made.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 10^3
- 1 ≤ value of coordinates ≤ 10^3
3 4 2 5 8 10 6 4 1 2 4 1 2 3 4 4 3 2 1 4 1 2 3 4 2 3 4 5Output:
2 1 4
case 1 :channels made will connect the pits loacted at position 8 and 10 in first lane to pits 1 and 2 in the second lane respectively without any blast.
case 2: Of all possible channels i.e. (1,4),(2,3),(3,2) and (4,1) ,at the most any one channel can be made since pits with equal index numbers are connected.
case 3:channels are made between (1,2),(2,3),(3,4)and(4,5) successfully.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.