P13305 [GCJ 2013 Finals] Can't Stop

桌游 Can't Stop 由 Sid Sackson 设计，曾由多家出版商发行。Sid Sackson 先生及各出版商均未参与 Google Code Jam，也未对本题进行任何背书。

本题灵感来源于 Sid Sackson 设计的桌游 Can't Stop。本题与该游戏有相似之处，但不要求你玩过 Can't Stop。 你正在玩一款（非常大）的桌面游戏。在这款游戏中，你会得到一个长度为 $N$ 的掷骰子序列。每组掷骰包含 $D$ 次骰子，每次掷骰得到一个整数。 你要赢得游戏，需要找到序列中最长的“超级棒区间”。一个区间指的是若干连续的掷骰组。如果存在 $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 组）是超级棒的，因为第 $0\sim 2$ 组都包含 $10, 50, 70$ 这三个数中的至少一个。区间 $[1,5]$ 是超级棒的，因为第 $1\sim 5$ 组都至少包含 $50, 30, 40$ 这三个数中的一个。这个区间包含 5 组掷骰，是最长的超级棒区间。 你的任务是输出最长超级棒区间的起止下标。如果有多个同样长度的超级棒区间，输出起始下标最小的那一个。注意，第一组掷骰编号为 0。

第一行为测试用例数 $T$。接下来的 $T$ 组数据，每组数据第一行为三个用空格分隔的整数 $N$、$D$、$k$，含义如上。下一行有 $N \times D$ 个整数。前 $D$ 个整数是第 0 组的结果，接下来的 $D$ 个整数是第 1 组的结果，依此类推。

对于每个测试用例，输出一行 `"Case #x: y z"`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 和 $z$ 分别为最长超级棒区间的起止下标（如有多解，取起始下标最小的）。

**限制条件** - $1 \leq T \leq 100$ - $1 \leq D \leq 4$ - $1 \leq \text{每次掷骰结果} \leq 10^5$ - 有 6 个测试点满足 $1 \leq N \leq 10^5$ - 其他测试点满足 $1 \leq N \leq 10^3$ **小数据集（11 分，测试集 1 - 可见）** - 时间限制：~~60~~ 6 秒 - $k = 2$ **大数据集（32 分，测试集 2 - 隐藏）** - 时间限制：~~120~~ 12 秒 - $2 \leq k \leq 3$ 翻译由 ChatGPT-4.1 完成。