#H. 【基础】评选最佳品牌

    Type: Default 1000ms 128MiB

【基础】评选最佳品牌

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

n 个评委投票,在 m 个商品中评选一个最佳品牌。 评选采用多轮淘汰制,即:每轮投票,淘汰掉得票最少的候选品牌(得票并列最少的品牌一起淘汰)。

如此一轮轮淘汰下去,如果最后只剩下一个品牌当选,即告评选成功。 但如果在某轮投票中,当时未被淘汰的所有候选品牌(大于等于两个品牌)都并列得票最少,即告评选失败。

如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。

在评选流程中,每个评委的态度都可用一个序列来表示;例如当 m=5 时,某评委的评选态度序列为:3、5、1、2、4,则表示该评委:优先投 3 号,当 3 号被淘汰时投 5 号,当 3 和 5 都被淘汰时投 1,当 3、5、1 都被淘汰时投 2,仅剩 4 号时才投 4 号品牌的票。

选票的序列中可以表示弃权,用 0 来表示,例如当 m=5 时,某评委的评选态度序列为:3、5、0,则表示该评委:优先投 3 号,当 3 号被淘汰时投 5 号,其它情况下不投任何品牌的票。

编程实现: 请你编一个程序,模拟各轮投票的过程,得到评选结果。

输入格式

第一行:MM(表示参加评选的品牌数)和 NN(表示参加投票的评委数),之间以空格分隔 接下来的 NN 行:每行都是长度不超MM的数字字符串,每个字符串表示一个评委的评选态度。

输出格式

输出评选结果

样例

3 4
123
213
132
10
1
3 4
321
213
231
312
-2

样例解释

样例1:

第一行3 4 代表3个品牌,4个评委。

第一轮投票,3个评委优先选择1号品牌,1个评委选择2号品牌,品牌3得票最少,淘汰掉;

第二轮投票,3个评委优先选择1号品牌,1个评委选择2号品牌,品牌2得票最少,淘汰掉; 淘汰2号品牌后,只剩一个1号品牌,1号品牌胜出,最终结果 1。

样例2: 第一行3 4 代表3个品牌,4个评委。

第一轮投票,2个评委选择2号品牌,两个评委选择3号品牌,1号得票最少,淘汰掉;

第二轮投票,2个评委选择2号品牌,两个评委选择3号品牌,由于只剩下两个品牌,且并列最少,都是2票,代表评选失败,需要输出最后一轮票数2的相反数-2,最终结果 -2。

数据范围

  • 1M101 \leq M \leq 10
  • 2N10002 \leq N \leq 1000

国庆七天乐

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
12
Start at
2024-10-2 12:15
End at
2024-10-8 0:15
Duration
132 hour(s)
Host
Partic.
72