OpenJudge

8:建水库

总时间限制:
1000ms
内存限制:
65536kB
描述

在一片湖泊和一片沙漠之间,恰好构成一个 N行M列 的矩形,如图所示,每个格子处有一个海拔高度。


只有与湖泊毗邻的第 1 行格子处可以建造水库。并且可以修建管道将水库的水输往海拔高度更低的格子,既“水往低处流”。

我们现在的目的是让靠近沙漠的 第N行 格子能用上水。能够想象到,在第一行中的某一格子建造水库,只能覆盖 第N行 的某几个格子。例如下图中,在3个框出的蓝、红、紫色格子建造水库,分别能够覆盖 第N行 的蓝、红、紫色区间。


本来你想保证建的水库数量越少越好,那么就存在一个应该在哪建水库的问题(区间覆盖);但是现在由于经费紧张,只能修建1个水库,此时肯定要保证 第N行 中能用上水的格子尽量多。

输入
第一行是两个正整数N和M(N,M <= 200),表示矩形的规模。接下来N行,每行M个正整数,依次代表每座城市的海拔高度,空格隔开。
输出
2行。
第1行输出第一行中水库的列号,若有多个最优解,请输出列号最小的那一个。
第2行,依次输出第N行中有水的格子列号,从1计数,空格隔开。
*注意,若不论在哪修建水库,都不能使第N行的格子用上水,请直接输出“Impossible!”。
样例输入
3 6
8 4 6 7 6 1
7 3 4 3 3 3
3 2 2 5 1 2
样例输出
4
2 3 5
全局题号
15374
添加于
2017-07-01
提交次数
8
尝试人数
5
通过人数
3