#504. 短码竞赛

传统 1000 ms 256 MiB
标准 IO
文本比较 匿名 标签

题目描述

短码竞赛(Code Golf)是一种趣味十足的程序设计竞赛。在短码竞赛中,参赛选手的目标不仅是解决一系列变成问题,而且要力求使用尽可能短的源代码来完成挑战。在比赛中,参赛选手往往使用高阶的程序设计技巧,甚至编写出看似“糟糕”的代码,以此来彰显他们的能力和创造力。

东南大学短码竞赛作为一项传统赛事,至今已有 11 年的传承。在这项赛事中,nn 名选手需要解决 mm 道编程题目。每位选手只有在正确解决问题的前提下,才有可能获得分数。对于每一道题目,所有成功解题的选手中,代码长度最短的选手将得到 100 分,而其他选手的得分将根据其代码长度相应递减。

具体来说,假设题目 jj 的最短正确代码长度为 bjb_j,而选手 ii 提交的代码长度为 ai,ja_{i,j},则该选手在题目 jj 上的得分为:

100bjai,j100^{\sqrt{\frac{b_j}{a_{i,j}}}}

每位选手的最终得分是他们在 mm 道题目上得分的总和。需要注意的是,如果选手 ii 未能正确解决某一题目,无论其他选手的表现如何,他都将无法获得该题的分数。

现在,给定 nn 名选手解决 mm 道题目的代码长度数据,你的任务是计算每位选手的最终得分,并找出得分最高的选手,输出其编号。

输入格式

第一行两个正整数 n,m(1n,m1000)n,m(1\le n,m\le 1000),分别表示参赛的选手数量和题目数量。

接下来 nn 行,第 ii 行包含 mm 个非负整数 ai,j(0ai,j103)a_{i,j}(0\le a_{i,j}\le 10^3),表示第 ii 位选手解答第 jj 道题目的代码长度。若 ai,j=0a_{i,j}=0,则表示该选手未能正确解答该题目。

输出格式

输出一个正整数,表示最终得分最高的选手编号。题目保证第一名选手的最终得分至少高出第二名 1.01.0 分。

样例

样例输入

3 3
109 0 208
100 0 0
130 4008 300

样例输出

3

样例说明

选手 1 的得分为 82.35+0+10082.35+0+100

选手 2 的得分为 100+0+0100+0+0

选手 3 的得分为 56.77+100+46.2756.77+100+46.27