问题1237--Rolnan只想要保底

1237: Rolnan只想要保底

[命题人 : ]
时间限制 : 1.500 sec  内存限制 : 128 MB

题目描述

题目背景

Rolnan是个非酋,因此任何和概率相关的事情,他只想要保底。

题目描述

在接下来的 \(n\) 天中,每天有 \(m\) 次抽奖机会。

用一个 \(n\cdot m\) 的矩阵 \(A\) 来表示,则 \(A_{i,j}\) 表示第 \(i\) 天的第 \(j\) 次抽奖机会中,Rolnan中奖的可能性。

Rolnan只有一次抽奖机会,但是他又想最大化中奖可能性,首先他会选择其中的两天 \(i,j\) 来抽奖,Rolnan会选择 \(A_{i,k},A_{j,k}\) 中的较大值 \(B_{i,j,k}=max\{A_{i,k},A_{j,k}\}\), 由于每个奖励Rolnan都想要,他会随机选择第 \(k\) 次来抽奖。

因为Rolnan是非酋,因此他希望能够最大化自己中奖的可能性,即要求选择两天\(i,j\),使得 \(min_{k=1}^{m}B_{i,j,k}\) 最大。

输入

第一行两个整数 \(n,m(1\leq n\leq 5\cdot10^4,1\leq m\leq 8)\)。

接下来 \(n\) 行,每行 \(m\) 个整数表示 \(A_{i,j},(0\leq A_{i,j}\leq 10^9)\)。

输出

输出两个整数 \(i,j\) ,表示选择的两天,使得结果最大。

如果存在多个解,输出字典序最小的组合\((i,j)\)。

注意,Rolnan可以选择同一天,即 \(i=j\)。

样例输入 Copy

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

样例输出 Copy

1 5

提示

对于样例1,选择 \(1,5\) 两天,这样 \(\forall k \in  [1,m], B_{1,5,k}\)的最小值为3,该值为所有选择中的最大值。