Клуб дебатов с \(n\) участниками, включая вас (участник \(1\)), сегодня последовательно обсудит \(k\) мнений. Во время каждого обсуждения участники выразят свое согласие или несогласие с мнением. Обозначим количество участников, которые согласны, как \(Y\), а количество участников, которые не согласны, как \(N\). После каждого обсуждения участники покидают клуб в соответствии со следующими правилами:
- Если больше участников согласны с мнением, чем не согласны (\(Y > N\)), все участники, которые не согласны, покидают клуб.
- Если больше участников не согласны с мнением, чем согласны (\(Y < N\)), все участники, которые согласны, покидают клуб.
- В случае ничьей (\(Y = N\)), все участники покидают клуб.
Как президент клуба, вы хотите остаться в клубе и максимизировать количество участников, оставшихся после встречи. Вы знаете позицию каждого участника по всем \(k\) мнениям до начала встречи, и вы можете исключить любых участников (кроме себя самого) перед началом встречи.
Определите максимальное количество участников, включая вас, которые могут остаться в клубе после встречи, при условии, что вы также останетесь в клубе после встречи.
Выходные данные
Для каждого набора входных данных выведите максимальное количество участников, включая вас, которые могут остаться в клубе после встречи.
Примечание
Для удобства, в примерах ниже мы будем разбирать ситуации, опираясь на то, кто пришел на встречу (т. е. не был исключен перед ней), а не на то, кто был исключён.
Пример 1:
На встречу мог прийти только первый участник, иначе оба участника ушли бы после обсуждения второго мнения.
Пример 2:
На встречу приходит только один участник и остается до конца.
Пример 3:
В клубе \(4\) участника, и только одно мнение будет обсуждаться во время встречи. Проанализируем возможные исходы в зависимости от участников на встрече:
- Если придет только первый участник, после встречи он останется один.
- Если первый участник придет со вторым или третьим участником, в обсуждении будет ничья, и они оба уйдут.
- Если первый участник придет со вторым и третьим участниками, первый участник окажется в меньшинстве и уйдет после обсуждения, что противоречит условию.
- Если придут первый и четвертый участники, они согласятся во время обсуждения и оба останутся до конца.
- Если придут первый, второй и четвертый участники, второй участник окажется в меньшинстве во время обсуждения, и после него останутся только первый и четвертый участники. То же самое произойдет, если второго участника заменить на третьего.
- Если придут все четыре участника, во время обсуждения будет ничья, и все уйдут.
Максимальное количество участников, оставшихся после встречи, составляет \(2\).
Пример 4:
В клубе \(5\) участников, и во время встречи будут обсуждаться \(4\) мнения.
Один из способов достичь максимального количества участников — если на встречу придут только первый, третий и пятый участники. В этом случае все они согласятся во время первых двух обсуждений, после чего третий участник окажется в меньшинстве во время третьего обсуждения. Затем первый и пятый участники согласятся в последнем обсуждении, и эти два участника останутся до конца встречи.
Пример 5:
В клубе \(4\) участника, и будут обсуждаться \(2\) мнения.
Если на встречу придут первые три участника, первый участник окажется в меньшинстве во время первого обсуждения и покинет клуб. После этого второй и третий участники будут не согласны со вторым мнением, и они оба останутся до конца встречи. Таким образом, после встречи останется 2 участника, но это недопустимый исход, так как это вынуждает первого участника уйти. Следовательно, максимальное количество в 1 участник достигается, если на встречу придет только первый участник.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2
++
+-
1 3
+-+
4 1
+
-
-
+
5 4
++++
+--+
++-+
+-++
++++
4 2
++
--
--
-+
|
1
1
2
2
1
|