题目背景

The board game Can't Stop was designed by Sid Sackson, and has been published by many publishers. Neither Mr. Sackson nor any of the publishers endorses, or has any involvement with, Google Code Jam.

题目描述

This problem was inspired by a board game called Can't Stop, designed by Sid Sackson. This problem has a similar idea, but does not assume you have played Can't Stop.

You're playing a (very large) board game. In this game, you're given a sequence of $N$ roll sets. Each roll set consists of $D$ die rolls. Each die roll is an integer.

To win the game, you have to find the largest totally awesome interval of the sequence. An interval is any consecutive sequence of roll sets. An interval is called totally awesome if there exist $k$ numbers such that every roll set in the interval contains at least one of those $k$ numbers.

For example, suppose $D=2$ and $k=3$, and the roll sets are as follows:

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

The interval from Set 0 to Set 2 is totally awesome because roll sets 0-2 all contain 10, 50 or 70. The interval from Set 1 to Set 5 is totally awesome because roll sets 1-5 all contain 50, 30 or 40. That interval contains 5 roll sets, and it is the largest totally awesome interval.

Your job is to output the indices of the first and last roll set in the longest totally awesome interval. If there are multiple totally awesome intervals of that length, output the indices for the one with the lowest first index. Note that the first roll set has index 0.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with three space-separated integers: $N$, $D$ and $k$, as described above. On the next line, there will be $N*D$ integers. The first $D$ integers will be the rolls from the first roll set; the second $D$ integers will be the rolls from the second roll set; and so on.

输出格式

For each test case, output one line containing "Case #x: $y$ $z$", where $x$ is the case number (starting from 1), and $y$ and $z$ are the first and last indices of the longest totally awesome interval (with ties broken using the lowest index), as described above.

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

提示

Limits

• $1 \leq T \leq 100.$
• $1 \leq D \leq 4.$
• $1 \leq \text{every die roll} \leq 10^5.$
• For 6 test cases, $1 \leq N \leq 10^5.$
• For all the other test cases, $1 \leq N \leq 10^3.$

Small dataset (11 Pts, Test set 1 - Visible)

• Time limit: 60 6 seconds.
• $k = 2.$

Large dataset (32 Pts, Test set 2 - Hidden)

• Time limit: 120 12 seconds.
• $2 \leq k \leq 3.$