5027: 评选最佳品牌(king)
[Creator : ]
Description
$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$ 号,其它情况下不投任何品牌的票。
请你编一个程序,模拟各轮投票的过程,得到评选结果。
评选采用多轮淘汰制,即:每轮投票,淘汰掉得票最少的候选品牌(得票并列最少的品牌一起淘汰)。
如此一轮轮淘汰下去,如果最后只剩下一个品牌当选,即告评选成功。
但如果在某轮投票中,当时未被淘汰的所有候选品牌(大于等于两个品牌)都并列得票最少,即告评选失败。
如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。
在评选流程中,每个评委的态度都可用一个序列来表示;例如当 $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$ 号,其它情况下不投任何品牌的票。
请你编一个程序,模拟各轮投票的过程,得到评选结果。
Input
第一行:$m\ (0<m<10)$,表示参加评选的品牌数和 $N\ (1<n<1000)$ 表示参加投票的评委数,
之间以空格分隔接下来的 $n$ 行:每行都是长度不超 $m$ 的数字字符串,每个字符串表示一个评委的评选态度。
之间以空格分隔接下来的 $n$ 行:每行都是长度不超 $m$ 的数字字符串,每个字符串表示一个评委的评选态度。
Output
评选结果。
Sample 1 Input
3 4
123
213
132
10
Sample 1 Output
1
第一行 $3\ 4$ 代表 $3$个品牌,$4$ 个评委。
第一轮投票,$3$ 个评委优先选择 $1$ 号品牌,$1$ 个评委选择 $2$ 号品牌,品牌 $3$ 得票最少,淘汰掉;
第二轮投票,$3$ 个评委优先选择 $1$ 号品牌,$1$ 个评委选择 $2$ 号品牌,品牌 $2$ 得票最少,淘汰掉;
淘汰 $2$ 号品牌后只剩一个 $1$ 号品牌,$1$ 号品牌胜出。
第一轮投票,$3$ 个评委优先选择 $1$ 号品牌,$1$ 个评委选择 $2$ 号品牌,品牌 $3$ 得票最少,淘汰掉;
第二轮投票,$3$ 个评委优先选择 $1$ 号品牌,$1$ 个评委选择 $2$ 号品牌,品牌 $2$ 得票最少,淘汰掉;
淘汰 $2$ 号品牌后只剩一个 $1$ 号品牌,$1$ 号品牌胜出。
Sample 2 Input
3 4
321
213
231
312
Sample 2 Output
-2
第一行 $3\ 4$ 代表 $3$ 个品牌 $4$ 个评委。
第一轮投票,$2$ 个评委选择 $2$ 号品牌,两个评委选择 $3$ 号品牌,$1$ 号得票最少,淘汰掉。
第二轮投票,$2$ 个评委选择 $2$ 号品牌,两个评委选择 $3$ 号品牌,由于只剩下两个品牌,且并列最少都是 $2$ 票,代表评选失败,需要输出最后一轮票数 $2$ 的相反数 $-2$。
最终结果 $-2$
第一轮投票,$2$ 个评委选择 $2$ 号品牌,两个评委选择 $3$ 号品牌,$1$ 号得票最少,淘汰掉。
第二轮投票,$2$ 个评委选择 $2$ 号品牌,两个评委选择 $3$ 号品牌,由于只剩下两个品牌,且并列最少都是 $2$ 票,代表评选失败,需要输出最后一轮票数 $2$ 的相反数 $-2$。
最终结果 $-2$