Bài toán này được lấy cảm hứng từ một trò chơi bàn cờ có tên là Can't Stop, được thiết kế bởi Sid Sackson. Bài toán này có ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi Can't Stop.

Bạn đang chơi một trò chơi bàn cờ (rất lớn). Trong trò chơi này, bạn được cung cấp một chuỗi gồm \(N\) bộ tung xúc xắc (roll sets). Mỗi bộ tung xúc xắc gồm \(D\) lần tung. Mỗi lần tung xúc xắc là một số nguyên.

Để thắng trò chơi, bạn phải tìm khoảng cực kỳ tuyệt vời (totally awesome interval) lớn nhất của chuỗi. Một khoảng là bất kỳ một đoạn liên tiếp các bộ tung xúc xắc nào. Một khoảng được gọi là cực kỳ tuyệt vời nếu tồn tại \(k\) số sao cho mọi bộ tung xúc xắc trong khoảng đó chứa ít nhất một trong \(k\) số đó.

Ví dụ, giả sử \(D=2\) và \(k=3\), và các bộ tung xúc xắc như sau:

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

Khoảng từ Bộ 0 đến Bộ 2 là cực kỳ tuyệt vời vì các bộ tung xúc xắc từ 0-2 đều chứa 10, 50 hoặc 70. Khoảng từ Bộ 1 đến Bộ 5 là cực kỳ tuyệt vời vì các bộ tung xúc xắc từ 1-5 đều chứa 50, 30 hoặc 40. Khoảng đó chứa 5 bộ tung xúc xắc, và đó là khoảng cực kỳ tuyệt vời lớn nhất.

Nhiệm vụ của bạn là xuất ra chỉ số của bộ tung xúc xắc đầu tiên và cuối cùng trong khoảng cực kỳ tuyệt vời dài nhất. Nếu có nhiều khoảng cực kỳ tuyệt vời cùng độ dài đó, hãy xuất ra các chỉ số của khoảng có chỉ số đầu tiên nhỏ nhất. Lưu ý rằng bộ tung xúc xắc đầu tiên có chỉ số là 0.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bắt đầu bằng ba số nguyên cách nhau bởi dấu cách: \(N\), \(D\) và \(k\), như mô tả ở trên. Trên dòng tiếp theo, sẽ có \(N \times D\) số nguyên. \(D\) số nguyên đầu tiên sẽ là các lần tung từ bộ tung xúc xắc đầu tiên; \(D\) số nguyên tiếp theo sẽ là các lần tung từ bộ tung xúc xắc thứ hai; và cứ tiếp tục như vậy.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng chứa "Case #x: y z", trong đó x là số thứ tự bộ test (bắt đầu từ 1), và y và z là chỉ số đầu tiên và cuối cùng của khoảng cực kỳ tuyệt vời dài nhất (ưu tiên chỉ số đầu tiên nhỏ nhất nếu có tranh chấp), như mô tả ở trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le D \le 4\).
• \(1 \le \text{mỗi lần tung xúc xắc} \le 10^5\).
• Đối với 6 bộ test, \(1 \le N \le 10^5\).
• Đối với tất cả các bộ test còn lại, \(1 \le N \le 10^3\).

Phân nhóm

• Small dataset (Test set 1 - Visible): \(k = 2\).
• Large dataset (Test set 2 - Hidden): \(2 \le k \le 3\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Trò chơi bàn cờ Can't Stop được thiết kế bởi Sid Sackson, và đã được xuất bản bởi nhiều nhà xuất bản. Cả ông Sackson và bất kỳ nhà xuất bản nào đều không xác nhận, hoặc có bất kỳ sự liên quan nào đến Google Code Jam.

Nguồn

Google Code Jam 2013, Chung kết thế giới, bài Can't Stop.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.