New Elements: Part 1

Hai đoạn đầu tiên của đề bài này (không tính đoạn ghi chú này) giống hệt hai đoạn đầu tiên của bài "New Elements: Part 2". Ngoài phần đó ra, hai bài có thể được giải độc lập; bạn không cần đọc hoặc giải bài này để đọc hoặc giải bài kia.

Muriel đang trên hành trình khám phá hai nguyên tố mới mà cô đặt tên là Codium và Jamarium. Cô chưa thể phân lập chúng, nhưng muốn bắt đầu gián tiếp nghiên cứu một số tính chất quan trọng, chẳng hạn như khối lượng nguyên tử. Vì Muriel đang làm việc với duy nhất một đồng vị của Codium và duy nhất một đồng vị của Jamarium, khối lượng nguyên tử của chúng là các số nguyên dương.

Muriel đã tạo ra \(N\) phân tử khác nhau; mỗi phân tử chứa một hoặc nhiều nguyên tử Codium, một hoặc nhiều nguyên tử Jamarium và không chứa nguyên tố nào khác. Với mỗi phân tử, cô biết số nguyên tử của từng nguyên tố có trong đó. Khối lượng phân tử bằng tổng khối lượng nguyên tử của tất cả các nguyên tử cấu thành phân tử ấy.

Là bước đầu tiên để xác định chính xác khối lượng phân tử và khối lượng nguyên tử của hai nguyên tố, Muriel muốn sắp xếp các phân tử theo khối lượng phân tử tăng nghiêm ngặt. Để đánh giá độ khó của công việc này, cô muốn biết có bao nhiêu thứ tự hợp lệ nếu chỉ xét những thông tin hiện có. Một thứ tự các phân tử được coi là hợp lệ nếu tồn tại một cách chọn khối lượng nguyên tử của Codium và Jamarium sao cho khối lượng phân tử trong thứ tự đó tăng nghiêm ngặt.

Ví dụ, ta biểu diễn mỗi phân tử bằng cặp có thứ tự gồm số nguyên tử Codium và số nguyên tử Jamarium mà nó chứa. Nếu Muriel có 3 phân tử được biểu diễn bởi \((1, 1)\), \((2, 1)\) và \((1, 2)\), có hai thứ tự có thể tăng nghiêm ngặt theo khối lượng phân tử: \((1, 1), (1, 2), (2, 1)\) và \((1, 1), (2, 1), (1, 2)\). Thứ tự đầu tiên hợp lệ với mọi cách gán khối lượng nguyên tử mà Codium là nguyên tố nặng hơn, còn thứ tự thứ hai hợp lệ với mọi cách gán mà Jamarium là nguyên tố nặng hơn. Trường hợp duy nhất còn lại là Codium và Jamarium có cùng khối lượng nguyên tử; khi đó \((1, 2)\) và \((2, 1)\) có cùng khối lượng phân tử, nên không thể tạo ra một thứ tự tăng nghiêm ngặt trong trường hợp này.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\), là số lượng phân tử. Mỗi dòng trong \(N\) dòng tiếp theo mô tả một phân tử khác nhau bằng hai số nguyên \(C_i\) và \(J_i\), lần lượt là số nguyên tử Codium và Jamarium trong phân tử thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in ra một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ 1) và y là tổng số thứ tự hợp lệ theo định nghĩa ở trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le C_i \le 10^9\) với mọi \(i\).
• \(1 \le J_i \le 10^9\) với mọi \(i\).
• \((C_i, J_i) \ne (C_j, J_j)\) với mọi \(i \ne j\). Mọi phân tử đều khác nhau.

Phân nhóm

Test Set 1 (Hiển thị)

• \(2 \le N \le 6\).

Test Set 2 (Ẩn)

• \(2 \le N \le 300\).

Đ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
3
1 1
1 2
2 1
4
1 2
2 4
2 1
4 2
3
1 2
1 3
2 3

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

Nguồn

Google Code Jam 2019, Vòng 2, bài New Elements: Part 1.

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