CF1453A.Cancel the Trains

入门

通过率:0%

时间限制:1.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Gildong's town has a train system that has 100100 trains that travel from the bottom end to the top end and 100100 trains that travel from the left end to the right end. The trains starting from each side are numbered from 11 to 100100, respectively, and all trains have the same speed. Let's take a look at the picture below.

The train system can be represented as coordinates on a 2D plane. The ii-th train starting at the bottom end is initially at (i,0)(i,0) and will be at (i,T)(i,T) after TT minutes, and the ii-th train starting at the left end is initially at (0,i)(0,i) and will be at (T,i)(T,i) after TT minutes. All trains arrive at their destinations after 101101 minutes.

However, Gildong found that some trains scheduled to depart at a specific time, simultaneously, are very dangerous. At this time, nn trains are scheduled to depart from the bottom end and mm trains are scheduled to depart from the left end. If two trains are both at (x,y)(x,y) at the same time for some xx and yy, they will crash into each other. Therefore, he is asking you to find the minimum number of trains that should be cancelled to prevent all such crashes.

吉尔东所在的城市有一个火车系统,其中包括 100 列从底端开往顶端的列车,以及 100 列从左端开往右端的列车。从每侧出发的列车分别编号为 11 至 100100,且所有列车速度相同。我们来看下面这张图。

该火车系统可在二维平面上用坐标表示。第 ii 列从底端出发的列车初始位置为 (i,0)(i,0),经过 TT 分钟后将到达 (i,T)(i,T);第 ii 列从左端出发的列车初始位置为 (0,i)(0,i),经过 TT 分钟后将到达 (T,i)(T,i)。所有列车均在 101 分钟后抵达各自的目的地。

然而,吉尔东发现,在某一特定时刻同时发车的若干列车存在极高风险。此时,有 nn 列列车计划从底端发车,另有 mm 列列车计划从左端发车。若两列列车在某一时刻同时位于同一坐标点 (x,y)(x,y)(其中 xx 和 yy 为实数),则它们将发生碰撞。因此,他请你计算:为避免所有此类碰撞,至少需要取消多少列列车。

输入格式

Each test contains one or more test cases. The first line contains the number of test cases tt (1≤t≤1001 \le t \le 100).

Each test case contains three lines. The first line of each test case consists of two integers nn and mm (1≤n,m≤1001 \le n, m \le 100) — the number of trains scheduled to depart from the bottom end, and the number of trains scheduled to depart from the left end, respectively.

The second line of each test case contains nn integers. Each integer is a train number that is scheduled to start from the bottom end. The numbers are given in strictly increasing order, and are between 11 and 100100, inclusive.

The third line of each test case contains mm integers. Each integer is a train number that is scheduled to start from the left end. The numbers are given in strictly increasing order, and are between 11 and 100100, inclusive.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1001 \le t \le 100)。

每个测试用例包含三行。每个测试用例的第一行包含两个整数 nn 和 mm(1≤n,m≤1001 \le n, m \le 100),分别表示计划从底端出发的列车数量和计划从左端出发的列车数量。

每个测试用例的第二行包含 nn 个整数。每个整数是一个计划从底端出发的列车编号。这些编号严格递增,且均在 11 到 100100(含)之间。

每个测试用例的第三行包含 mm 个整数。每个整数是一个计划从左端出发的列车编号。这些编号严格递增,且均在 11 到 100100(含)之间。

输出格式

For each test case, print a single integer: the minimum number of trains that should be canceled in order to prevent all crashes.

对于每个测试用例,输出一个整数:为防止所有碰撞而必须取消的最少列车数量。

输入输出样例

  • 输入#1

    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

    输出#1

    0
    1
    3

说明/提示

In the first case, we can show that there will be no crashes if the current schedule is followed. Therefore, the answer is zero.

In the second case, at T=4T=4, there will be a crash, as can be seen in the picture below. We can prove that after canceling one of these trains, the remaining trains will not crash. Therefore, the answer is one.

在第一种情况下,我们可以证明:如果按照当前的时刻表运行,则不会发生碰撞。因此,答案为零。

在第二种情况下,在 T=4T=4 时刻将发生碰撞,如下图所示。我们可以证明:取消其中一列火车后,其余火车将不会发生碰撞。因此,答案为一。

输入解题思路,AI测评打分。不知道怎么写?

首页