| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1419
校赛的奖品投票
Time Limit: 2000ms
Memory Limit: 65536kb Description
USTC-ACM 要办校赛啦, 前期进行了一轮关于奖品意向的问卷调查, 很多同学都投票选出了自己喜欢的奖品, 现在搜集到 n 个同学的偏好信息, 每个同学按自己的喜好, 把 m 件备选的奖品做了喜好的排序, 排在前的喜好程度更高. 现在需要票选冠军的奖品, 票选的过程是这样的: 备选的奖品一件件地被投票, 如果大于等于 50% 的同学赞成这个奖品作为冠军奖励,那么票选结束, 不再继续投票之后的备选奖品. 否则继续投票下一种奖品, 直到所有奖品都被票选过.如果仍然没有大于等于50% 的同学同时赞成一个奖品作为奖励, 那么冠军将没有奖品. 现在, 我们假设每个同学都非常聪明, 他们知道彼此都是很聪明的, 他们投票的时候会采取最优策略, 以使得最后的冠军奖励是自己更偏好的.(每个同学都更希望冠军是有奖品的), 那么请问最后的冠军奖励会是那件奖品呢? Input
输入包含多组数据, 输入数据的第一行是一个正整数 T , (1 ≤ T ≤ 50), 表示共有T 组数据, 之后每组数据具有如下形式: 第一行是两个正整数 n, 和 m,(1 ≤ n, m ≤ 500), 分别表示有 n 个同学参加投票,m 件奖品候选. 第二行有 m个字符串, 表示依次被投票的奖品的名称, 保证每个字符串长度在 1 到 10 之间,且没有奖品的名字是一样的. 奖品的名字只包含大小写字母和数字. 之后的 n行, 每行有 m 个字符串, 表示第 i 个同学, 关于 m 个奖品的偏好排序,(排在前面表示更喜欢). 保证这 m 个字符串是被投票的 m 种奖品的名字的一个排列. Output
对每组数据输出, 请输出单独一行”Case #x: name”, 其中 x 表示数据组数,(从1 开始标号),name 表示最终会成为冠军奖励的奖品的名称. 请不要输出多余的空格或空行.(详见样例).
Sample Input
2 1 2 Cherry Kindle Cherry Kindle 2 3 Kindle SSD Cherry Kindle Cherry SSD SSD Kindle Cherry Sample Output
Case #1: Cherry Case #2: Kindle Hint
题面更正! 大于等于50% 就能作为奖品.造成的困扰深表抱歉.第二个样例, 票选 Kindle 的时候如果第二个人不投赞同票, 那么之后票选 SSD的时候, 第一个人会反对 SSD, 所以进行 Cherry 的投票, 显然有奖品比没奖品好,大家都会同意 Cherry. 所以这样的情况下, 奖品是 Cherry, 但是比起Cherry,Kindle 更受第二个人的喜爱, 所以他会在投 Kindle 的时候就同意. 所以答案是 Kindle. 更正: 前面的解释是针对大于50%的, 因为是大于等于50%,那么第一个人投赞成就会是Kindle了,这也是最好的结果. 本题FB奖: 精美书包一个. Source
yuzhou627
|