Mysterious Road Signs

Thị trấn Signfield nằm trên một con đường thẳng hoàn hảo và dài vô hạn chạy từ tây sang đông. Dọc theo con đường có một dãy \(S\) biển báo bí ẩn với các con số ở cả hai mặt. Biển thứ \(i\) (được đánh số theo thứ tự từ tây sang đông) nằm tại một điểm cách Signfield \(D_i\) kilômét về phía đông, có số \(A_i\) ở mặt quay về phía tây và số \(B_i\) ở mặt quay về phía đông.

Không ai ở Signfield biết những biển báo này muốn nói gì. Bạn cho rằng các số ở mặt phía tây dành cho tài xế đi về hướng đông và biểu thị khoảng cách đến một địa điểm cụ thể nào đó. Tương tự, bạn cho rằng các số ở mặt phía đông dành cho tài xế đi về hướng tây và biểu thị khoảng cách đến một địa điểm cụ thể nào đó. Tuy nhiên, bạn nghi ngờ rằng không phải tất cả biển báo đều nhất quán với giả thuyết này.

Để bắt đầu kiểm chứng giả thuyết, bạn muốn tìm các tập biển báo hợp lệ tuân theo những quy tắc sau:

• Tập đó là một dãy con liên tiếp của toàn bộ dãy biển báo. (Cả toàn bộ dãy cũng được tính là một dãy con liên tiếp.)
• Tồn tại hai vị trí \(M\) và \(N\) kilômét về phía đông Signfield, trong đó \(M\) và \(N\) là các số không nhất thiết dương và không nhất thiết phân biệt, sao cho với mỗi biển trong tập, ít nhất một trong hai điều sau đúng:
  • \(D_i+A_i=M\).
  • \(D_i-B_i=N\).

Số biển lớn nhất có thể có trong một tập hợp lệ như mô tả ở trên là bao nhiêu, và có bao nhiêu tập hợp lệ khác nhau có kích thước đó?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa số nguyên \(S\): số biển báo. Sau đó có thêm \(S\) dòng. Dòng thứ \(i\) mô tả biển thứ \(i\) (theo thứ tự từ tây sang đông) và chứa ba số nguyên \(D_i\), \(A_i\), \(B_i\): khoảng cách của biển về phía đông Signfield (tính bằng kilômét), số trên mặt phía tây và số trên mặt phía đông.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y và z lần lượt là số biển lớn nhất có thể có trong một tập hợp lệ và số tập hợp lệ có kích thước đó, như mô tả trong đề bài.

Ràng buộc

• \(1\le T\le60\).
• \(1\le D_i\le10^6\) với mọi \(i\).
• \(D_i<D_j\) với mọi \(i<j\).
• \(1\le A_i\le10^6\) với mọi \(i\).
• \(1\le B_i\le10^6\) với mọi \(i\).

Phân nhóm

Test Set 1 (Hiển thị): \(1\le S\le100\) trong mọi bộ test.

Test Set 2 (Ẩn): \(1\le S\le100\) trong tất cả trừ 3 bộ test; trong 3 bộ test còn lại, \(S=10^5\).

Đ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ụ

3
1
1 1 1
5
2 7 12
6 3 11
8 10 1
11 11 12
13 9 14
5
1 3 3
2 2 2
3 1 1
4 2 2
5 3 3

Case #1: 1 1
Case #2: 3 2
Case #3: 5 1

Nguồn

Google Code Jam 2018, Vòng 1B, bài Mysterious Road Signs.

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