CF1453A.Cancel the Trains

传统题 时间 2000 ms 内存 256 MiB 3 尝试 1 已通过 1 标签

Cancel the Trains

题目描述

Gildong 有一列车系统。从左到右,从下到上分别有 100100 头列车。从每侧出发的列车从 11100100 编号,所有列车的速度相同。如图。

列车系统可以用二维平面上的坐标表示。每一头列车视为一个点,从底部开始的第 ii 头列车最初在 (i,0)(i,0) ,并将在 TT 分钟后到达 (i,T)(i,T),从左端开始的第 ii 列车最初在 (0,i)(0,i) ,在 TT 分钟后将在 (T,i)(T,i) 开始。所有列车在 101101 分钟后到达目的地。

然而,Gildong 发现,一些在特定时间发车的列车,是存在危险的。这时,有 nn 头列车计划从底端发车,mm 列车计划从左端发车。如果两列火车同时处于 (x,y)(x,y) 的位置,那么它们会相撞。因此,Gildong 要求你找出应该取消的最小列车数,以防止所有碰撞发生。

输入格式

每个数据点包含一个或多组数据。第一行包含测试组数 t(1t100)t (1\le t\le 100)

每个测试数据包含三行。

第一行两个整数 nnm(1n,m100)m (1\le n,m\le 100),代表计划从底端出发的列车数和计划从左端出发的列车数。

第二行包含 nn 个整数。每个整数代表从底端开始的列车号。这些数字是按严格递增的顺序给出的,介于 11100100 之间(含 11100100)。

第三行包含 mm 个整数。每个整数代表从左端开始的列车号。这些数字是按严格递增的顺序给出的,介于 11100100 之间(含 11100100)。

输出格式

对于每个测试用例,输出一个整数:为了防止所有碰撞,应该取消的最小列车数。

说明/提示

对于第一组数据,可以证明,无论什么时候,都不会发生碰撞。因此,答案是 00

对于第二组数据,当 T=4T=4时,会发生碰撞,如图所示。可以证明,取消其中一头列车后,剩下的火车不会相撞。因此,答案是 11

样例

3
1 2
1
3 4
3 2
1 3 4
2 4
9 14
2 7 16 28 33 57 59 86 99
3 9 14 19 25 26 28 35 41 59 85 87 99 100
0
1
3

在线编程 IDE

建议全屏模式获得最佳体验