停不下来 - 問題

这个问题灵感来源于 Sid Sackson 设计的棋盘游戏《Can't Stop》。本题采用了类似的理念，但并不要求你玩过《Can't Stop》。

你正在玩一个（非常大的）棋盘游戏。在这个游戏中，你将获得一个包含 $N$ 个掷骰子集合的序列。每个集合由 $D$ 次掷骰结果组成。每次掷骰的结果都是一个整数。

为了赢得游戏，你需要找到序列中最长的“完全棒”（totally awesome）区间。区间是指掷骰集合的任意连续序列。如果存在 $k$ 个数字，使得该区间内的每一个掷骰集合都至少包含这 $k$ 个数字中的一个，那么这个区间就被称为“完全棒”的。

例如，假设 $D=2$ 且 $k=3$，掷骰集合如下：

集合 0: 10 20 集合 1: 50 60 集合 2: 70 30 集合 3: 40 40 集合 4: 30 30 集合 5: 20 40

从集合 0 到集合 2 的区间是“完全棒”的，因为集合 0-2 都包含 10、50 或 70。从集合 1 到集合 5 的区间是“完全棒”的，因为集合 1-5 都包含 50、30 或 40。该区间包含 5 个掷骰集合，它是最长的“完全棒”区间。

你的任务是输出最长“完全棒”区间中第一个和最后一个掷骰集合的索引。如果存在多个相同长度的“完全棒”区间，则输出第一个索引最小的那个区间的索引。注意，第一个掷骰集合的索引为 0。

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以三个空格分隔的整数 $N$、$D$ 和 $k$ 开头，如上所述。下一行包含 $N \times D$ 个整数。前 $D$ 个整数是第一个掷骰集合的结果；接下来的 $D$ 个整数是第二个掷骰集合的结果，以此类推。

对于每个测试用例，输出一行 "Case #x: y z"，其中 $x$ 是用例编号（从 1 开始），$y$ 和 $z$ 是最长“完全棒”区间的第一个和最后一个索引（若长度相同，则取第一个索引最小的），如上所述。

$1 \le T \le 100$ $1 \le D \le 4$ $1 \le \text{每次掷骰结果} \le 10^5$ 对于 6 个测试用例，$1 \le N \le 10^5$。对于所有其他测试用例，$1 \le N \le 10^3$。

4
8 1 2
1 2 3 2 4 5 4 6
4 3 2
1 2 3 4 5 6 7 8 9 10 11 12
6 2 3
10 20 50 60 70 30 40 40 30 30
20 40
10 1 3
2 4 3 1 4 5 3 1 1 2

Case #1: 1 3
Case #2: 0 1
Case #3: 1 5
Case #4: 1 4

QOJ.ac