[湖南集训] Hungry Rabbit
题目描述
可怕的洪水在夏天不期而至,兔子王国遭遇了前所未有的饥荒,它们不得不去外面的森林里寻找食物。
为了简化起见,我们假设兔子王国中有 $n$ 只兔子,编号为 $1$ 到 $n$。在救济粮到来之前的 $m$ 天中,每天恰好有 $k$ 只兔子需要去森林里寻找粮食。森林里居住着可怕的大灰狼,所幸兔子已经摸清了大灰狼捕食习惯,即狼们在每一天只会捕食特定编号的兔子。为了安全起见,兔子们需要保证每次出去觅食的 $k$ 只兔子都不会被狼捕食。
由于每天出去捕食的兔子都不尽相同,它们为每一天定义了一个生疏度 $p_i$ ,即第 $i$ 天出来寻找食物,但是第 $i−1$ 天却没有出来觅食的兔子个数。规定第 $1$ 天的生疏度为 $0$。
现在兔子们希望在保证安全的前提下,每天的生疏度不能超过 $l$,请为兔子们构造一个合法的方案。
输入输出格式
输入格式
第一行包括四个整数 $n, m, k, l$。
接下来 $n$ 行,每行一个长度为 $m$ 的 $01$ 串。其中第 $i$ 行第 $j$ 个字符若为 $0$,则表示狼在第 $j$ 天会捕食编号为 $i$ 的兔子,为 $1$ 则表示不捕食。
输出格式
共 $m$ 行,每行 $k$ 个 $1$ 到 $n$ 之间互不相同的整数,代表这一天出去寻找食物的兔子编号。
如果没有合法方案,则输出一行 `−1` 即可。
输入输出样例
输入样例 #1
5 4 3 1
1001
1101
1111
1110
0111
输出样例 #1
2 3 4
2 3 4
3 4 5
2 3 5
说明
#### 样例 1 解释
对于样例,在这 $4$ 天中,出去觅食的兔子集合分别为 $\{2, 3, 4\}; \{2, 3, 4\}; \{3, 4, 5\}; \{2, 3, 5\}$。
---
#### 数据规模与约定
- 对于 $20\%$ 的测试数据,保证 $1\leq n,m\leq 10$;
- 对于 $100\%$ 的测试数据,保证 $1\leq n,m\leq 800,$,$1\leq k\leq n$,$1\leq l\leq k$。