← 返回题目列表

Codeforces · 1818/A

A. 政治

中文机器翻译题面 查看原题

在一个拥有 $$$n$$$ 成员(包括你自己(成员 $$$1$$$))的辩论俱乐部中,有 $$$k$$$ 个观点需要按顺序讨论。在每次讨论中,成员都会表达他们同意或不同意的观点。我们将 $$$Y$$$ 定义为同意的成员数量,将 $$$N$$$ 定义为不同意的成员数量。每次讨论后,会员根据以下标准离开俱乐部:

- 如果同意的成员多于不同意的成员 ($$$Y > N$$$),则所有不同意的成员离开俱乐部。
- 如果不同意的成员多于同意的成员 ($$$Y < N$$$),则所有同意的成员都会离开俱乐部。
- 如果平局 ($$$Y = N$$$),则所有成员离开俱乐部。

作为俱乐部主席,您的目标是留在俱乐部并最大限度地增加会议后剩余的会员数量。在会议开始之前,您可以了解每个成员对所有 $$$k$$$ 意见的立场,并且您可以在会议开始之前驱逐任意数量的成员(不包括您自己)。

确定会议结束后可以留在俱乐部的会员(包括您自己)的最大人数。您无需提供具体的驱逐策略,只需提供可以留下的最大成员数即可。确保会议结束后您也留在俱乐部。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个正整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 100$$$) — 成员数量和讨论数量。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含长度为 $$$k$$$ 的字符串 $$$t_i$$$。字符串 $$$t_i$$$ 中的第 $$$j$$$ 个字符指示第 $$$i$$$ 个成员是否同意或不同意第 $$$j$$$ 个意见(如果他们在该讨论期间在场)。 “+”号表示会员同意,“-”号表示会员不同意。

保证所有测试用例的 $$$n \cdot k$$$ 总和不超过 $$$5 \cdot 10^4$$$。

输出

对于每个测试用例,输出会议结束后可以留在俱乐部的成员(包括您自己)的最大数量。

示例

输入 #1

5
2 2
++
+-
1 3
+-+
4 1
+
-
-
+
5 4
++++
+--+
++-+
+-++
++++
4 2
++
--
--
-+

输出 #1

1
1
2
2
1

注意

为了方便起见,我们将根据实际参加会议的人员(即未被开除)而不是被开除的人员来分析示例。

示例 1:

只有第一个成员可以参加会议,否则在讨论第二个意见后,两个成员都会离开。

示例 2:

只有一名成员出席会议并留到最后。

示例 3:

俱乐部有 $$$4$$$ 会员,会议期间只会讨论一种意见。让我们根据会议参与者来分析可能的结果:

- 如果只有第一位成员参加,那么他们将是会议结束后剩下的唯一成员。
- 如果第一个成员与第二个或第三个成员一起参加,他们将在讨论中打平,导致他们双双离开。
- 如果第一个成员与第二个和第三个成员一起参加,则第一个成员将成为少数成员,并将在讨论后离开,这与声明相矛盾。
- 如果第一名和第四名成员出席,他们将在讨论过程中达成一致,并且两人都会留到最后。
- 如果第一、第二和第四位成员参加,则第二位成员在讨论过程中将成为少数,最后只剩下第一和第四位成员。如果第二个成员被第三个成员替换,也会发生同样的情况。
- 如果四名成员都参加,讨论过程中就会出现平局,导致所有人离开。

会议结束后剩余成员的最大人数为$$$2$$$。

示例 4:

俱乐部有$$$5$$$会员,会议期间将讨论$$$4$$$意见。

实现最大成员人数的一种方法是只有第一、第三和第五名成员参加会议。在这种情况下,他们在前两次讨论中都同意,之后在第三次讨论中第三个成员处于少数。然后,第一名和第五名成员在最后一次讨论中达成一致,这两名成员留到会议结束。

示例 5:

俱乐部有 $$$4$$$ 会员,将讨论 $$$2$$$ 意见。

如果前三名成员出席会议,则第一位成员在第一次讨论中将属于少数派,并将离开俱乐部。之后,第二名和第三名成员均不同意第二个意见,并留至会议结束。这样,会议结束后就会剩下2名成员,但这是一个无效的结果,因为它迫使第一个成员离开。因此,如果只有第一位成员出席会议,则达到 1 名成员的最大人数。