← 返回题目列表

Codeforces · 1267/E

E. 选举

中文机器翻译题面 查看原题

Byteburg 参议院选举即将到来。通常,执政的拜特兰党“联合拜特兰”占据参议院的所有席位,以确保稳定和可持续发展。但今年其中一个选区出现了一名反对派候选人。即使是一名反对党议员也会扰乱参议院的稳定,因此党魁请您确保反对党候选人不会当选。

有 $$$n$$$ 个候选人,编号从 1 到 $$$n$$$。候选人$$$n$$$ 是反对党候选人。该选区有 $$$m$$$ 投票站,编号从 1 到 $$$m$$$。您知道每个投票站每位候选人的票数。为了阻止反对派候选人当选,你唯一能做的就是取消一些投票站的选举结果。如果在所有未取消的站点上投给反对派候选人的票数总和严格大于所有其他候选人的类似总和,则反对派候选人将当选。

你的任务是通过在尽可能少的投票站取消选举结果来阻止反对派候选人当选。请注意,解决方案始终存在,因为如果取消所有投票站的选举,则每个候选人的票数将为 0,反对派候选人将不会当选。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\le n\le 100$$$; $$$1\le m \le 100$$$) — 候选人数量和投票站数量。接下来的 $$$m$$$ 行包含每个投票站的选举结果,每行上有 $$$n$$$ 数字。在第 $$$i$$$ 行中,第 $$$j$$$ 数字是 $$$a_{i,j}$$$ — 在 $$$i$$$ 站为候选人 $$$j$$$ 投出的票数 ($$$0\le a_{i,j} \le 1\,000$$$)。

输出

第一行输出整数 $$$k$$$ — 需要取消选举结果的最少投票站数量。在第二行中输出 $$$k$$$ 整数 - 已取消投票站的索引,按任意顺序排列。如果有多种方法可以取消 $$$k$$$ 站的结果,则输出其中任何一种。

示例

输入 #1

5 3
6 3 4 2 8
3 7 5 6 7
5 2 4 7 9

输出 #1

2
3 1

输入 #2

2 1
1 1

输出 #2

0

输入 #3

3 3
2 3 8
4 2 9
3 1 7

输出 #3

3
1 2 3

注意

在第一个示例中,1 至 5 号候选人分别获得了 14、12、13、15 和 24 票。反对党候选人得票最多。然而,如果取消第一和第三投票站的选举结果,则只剩下第二投票站的结果,得票数变为3、7、5、6和7,反对派候选人不再领先。