310349: CF1818A. Politics
Description
In a debate club with $n$ members, including yourself (member $1$), there are $k$ opinions to be discussed in sequence. During each discussion, members express their agreement or disagreement with the opinion. Let's define $Y$ as the number of members who agree and $N$ as the number of members who disagree. After each discussion, members leave the club based on the following criteria:
- If more members agree than disagree ($Y > N$), all members who disagreed leave the club.
- If more members disagree than agree ($Y < N$), all members who agreed leave the club.
- If there is a tie ($Y = N$), all members leave the club.
As the club president, your goal is to stay in the club and maximize the number of members remaining after the meeting. You have access to each member's stance on all $k$ opinions before the meeting starts, and you can expel any number of members (excluding yourself) before the meeting begins.
Determine the maximum number of members, including yourself, who can remain in the club after the meeting. You don't need to provide the specific expulsion strategy but only the maximum number of members that can stay. Ensure that you remain in the club after the meeting as well.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.
The first line of each test case contains two positive integers $n$ and $k$ ($1 \le n, k \le 100$) — the number of members and the number of discussions.
The $i$-th of the following $n$ lines contains a string $t_i$ of length $k$. The $j$-th character in the string $t_i$ indicates whether the $i$-th member agrees or disagrees with the $j$-th opinion if they are present during that discussion. A "+" symbol means the member agrees, while a "-" symbol means the member disagrees.
It is guaranteed that the sum of $n \cdot k$ over all test cases does not exceed $5 \cdot 10^4$.
OutputFor each test case, output the maximum number of members, including yourself, who can remain in the club after the meeting.
ExampleInput5 2 2 ++ +- 1 3 +-+ 4 1 + - - + 5 4 ++++ +--+ ++-+ +-++ ++++ 4 2 ++ -- -- -+Output
1 1 2 2 1Note
For convenience, we will analyze the examples based on who actually attended the meeting (i. e. was not expelled) rather than who was expelled.
Example 1:
Only the first member could have attended the meeting, otherwise both members would have left after the second opinion is discussed.
Example 2:
There is only a single member that attends the meeting and stays till the end.
Example 3:
The club has $4$ members and only one opinion will be discussed during the meeting. Let's analyze the possible outcomes based on the participants in the meeting:
- If only the first member attends, they'll be the only one left after the meeting.
- If the first member attends with the second or third member, they will be a tie in the discussion, making them both leave.
- If the first member attends with the second and third members, the first member will be in the minority and will leave after the discussion, which contradicts the statement.
- If the first and fourth members attend, they will agree during the discussion and both remain till the end.
- If the first, second, and fourth members attend, the second member will be in the minority during the discussion, and only the first and fourth members will remain at the end. The same happens if the second member is replaced by the third member.
- If all four members attend, there will be a tie during the discussion, making everyone leave.
The maximum number of members remaining after the meeting is $2$.
Example 4:
The club has $5$ members and $4$ opinions will be discussed during the meeting.
One way to achieve the maximum number of members is if only the first, third, and fifth members attend the meeting. In this case, they all agree during the first two discussions, after which the third member is in the minority during the third discussion. Then, the first and fifth members agree in the last discussion, and those two members stay till the end of the meeting.
Example 5:
The club has $4$ members and $2$ opinions will be discussed.
If the first three members attend the meeting, the first member will be in the minority during the first discussion and will leave the club. After that, the second and third members will both disagree with the second opinion, and they both will stay till the end of the meeting. In this way, there will be 2 members left after the meeting, but it is an invalid outcome, as it forces the first member to leave. Therefore, the maximum number of 1 member is achieved if only the first member attends the meeting.
Input
题意翻译
## 题目描述 在一个有着 $n$ 个成员的辩论俱乐部中（你是其中的第 $1$ 个成员），有 $k$ 个辩题即将被按顺序辩论。在每次辩论中，俱乐部的成员们会表达他们同意或者不同意这个辩题。我们假设有 $Y$ 个成员同意， $N$ 个成员不同意。在每次辩论之后，成员们会按照以下的规则退出俱乐部： + 如果同意的成员多于不同意的成员（ $Y > N$ ），那么所有不同意的成员会退出俱乐部； + 如果不同意的成员多于同意的成员（ $Y < N$ ），那么所有同意的成员会退出俱乐部； + 如果平局（ $Y = N$ ），那么所有成员都会退出俱乐部。 作为俱乐部的部长，你的目标是让自己待在俱乐部里，并且使辩论之后俱乐部里剩余的成员的数量最大化。在辩论开始之前，你已经得知了每一位成员对于各个辩题的意见，并且你可以在辩论开始之前开除任意数量的成员（不包括你自己）。 你需要求出辩论之后俱乐部里最多能剩下多少人（包括你自己）。你不需要输出开除的方案。请确保最后你自己还在俱乐部里。 ## 输入格式 每个测试点包含多组数据。输入数据的第一行包含数据组数 $t$ ( $1 \le t \le 100$ )。第二行及以下是测试数据。 每组测试数据的第一行包含两个正整数 $n$ 和 $k$ ( $1 \le n,k \le 100$ )，分别表示俱乐部内成员的个数和辩题的个数。 接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $k$ 的字符串 $t_i$ 。字符串 $t_i$ 中的第 $j$ 个字符（ $+$ 或 $-$ ）描述了第 $i$ 位成员对第 $j$ 个辩题的意见（如果这时候他/她还在俱乐部中）。“ $+$ ”代表同意，而“ $-$ ”代表不同意。 输入保证各组数据的 $n \sdot k$ 之和不超过 $5 \sdot 10^4$ 。 ## 输出格式 对于每组数据，输出辩论之后俱乐部里最多能剩下的人数。Output
在一个辩论俱乐部中，包括你自己（成员1）共有n名成员，有k个观点需要依次讨论。在每次讨论中，成员们会表达他们对观点的支持或反对。定义Y为同意的成员数，N为不同意的成员数。每次讨论后，成员会根据以下标准离开俱乐部：
- 如果同意的成员多于不同意的（Y > N），所有不同意的成员离开俱乐部。
- 如果不同意的成员多于同意的（Y < N），所有同意的成员离开俱乐部。
- 如果平局（Y = N），所有成员离开俱乐部。
作为俱乐部主席，你的目标是留在俱乐部中，并最大化会议结束后剩余的成员数。你可以在会议开始前驱逐任何数量的成员（不包括你自己）。
确定会议结束后可以留在俱乐部的最大成员数，包括你自己。你不需要提供具体的驱逐策略，只需提供可以留下的最大成员数。确保会议结束后你自己也在俱乐部中。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。
- 每个测试用例的第一行包含两个正整数n和k（1 ≤ n, k ≤ 100），分别表示成员数和讨论数。
- 接下来的n行，每行包含一个长度为k的字符串ti。字符串ti的第j个字符表示如果第i个成员在第j次讨论时在场，他对该观点是支持还是反对。"+"符号表示支持，"-"符号表示反对。
保证所有测试用例的n*k之和不超过5*10^4。
输出：
- 对于每个测试用例，输出会议结束后可以留在俱乐部的最大成员数，包括你自己。题目大意： 在一个辩论俱乐部中，包括你自己（成员1）共有n名成员，有k个观点需要依次讨论。在每次讨论中，成员们会表达他们对观点的支持或反对。定义Y为同意的成员数，N为不同意的成员数。每次讨论后，成员会根据以下标准离开俱乐部： - 如果同意的成员多于不同意的（Y > N），所有不同意的成员离开俱乐部。 - 如果不同意的成员多于同意的（Y < N），所有同意的成员离开俱乐部。 - 如果平局（Y = N），所有成员离开俱乐部。 作为俱乐部主席，你的目标是留在俱乐部中，并最大化会议结束后剩余的成员数。你可以在会议开始前驱逐任何数量的成员（不包括你自己）。 确定会议结束后可以留在俱乐部的最大成员数，包括你自己。你不需要提供具体的驱逐策略，只需提供可以留下的最大成员数。确保会议结束后你自己也在俱乐部中。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。 - 每个测试用例的第一行包含两个正整数n和k（1 ≤ n, k ≤ 100），分别表示成员数和讨论数。 - 接下来的n行，每行包含一个长度为k的字符串ti。字符串ti的第j个字符表示如果第i个成员在第j次讨论时在场，他对该观点是支持还是反对。"+"符号表示支持，"-"符号表示反对。 保证所有测试用例的n*k之和不超过5*10^4。 输出： - 对于每个测试用例，输出会议结束后可以留在俱乐部的最大成员数，包括你自己。