Cancel the Trains
Time limit1sMemory limit512 MB
Given two sorted lists of train numbers, count how many numbers appear in both, since only trains with the same number can crash.
- Level
Easy2 of 10
- Topics
- Array, Two pointers
- Solved
- No attempts yet
Problem
Gildong's town has a train system with trains that travel from the bottom end to the top end and trains that travel from the left end to the right end. The trains starting from each side are numbered from to , and all trains have the same speed. Look at the picture below.

The train system can be represented as coordinates on a 2D plane. The -th train starting at the bottom end is initially at and will be at after minutes. The -th train starting at the left end is initially at and will be at after minutes. All trains arrive at their destinations after minutes.
Gildong found that some trains scheduled to depart at the same time are very dangerous. At this time, trains are scheduled to depart from the bottom end and trains from the left end. If two trains are both at at the same time for some and , they crash. Find the minimum number of trains that must be cancelled to prevent all crashes.
Input
The first line contains the number of test cases ().
Each test case has three lines. The first line contains two integers and (), the number of trains departing from the bottom end and the left end. The second line contains integers, the train numbers departing from the bottom end. The third line contains integers, the train numbers departing from the left end. Each number is between and , inclusive, and the numbers are given in strictly increasing order.
Output
For each test case, print one integer: the minimum number of trains to cancel to prevent all crashes.
Hint
In the first case, no crash occurs if the current schedule is followed, so the answer is zero.
In the second case, a crash occurs at , as shown in the picture below. Cancelling one of these trains leaves the remaining trains with no crashes, so the answer is one.
