Nguyên tố mới: Phần 2

Hai đoạn đầu tiên (không tính đoạn này) của bài toán này và bài "Nguyên tố mới: Phần 1" là giống hệt nhau. Ngoài 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ó thể đọc hoặc giải bài kia.

Muriel đang trên đường khám phá hai nguyên tố mới mà cô đặt tên là Codium và Jamarium. Cô vẫn chưa thể tách riêng 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 chỉ làm việc với một đồng vị duy nhất của Codium và một đồng vị duy nhất 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 được \(N\) phân tử khác nhau. Mỗi phân tử chứa ít nhất một nguyên tử Codium, ít nhất một 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ử mà phân tử chứa.

Bước đầu tiên, Muriel sắp xếp các phân tử theo thứ tự khối lượng phân tử tăng nghiêm ngặt. Bây giờ, cô muốn tìm các giá trị nguyên khả dĩ cho khối lượng nguyên tử của cả Codium lẫn Jamarium sao cho phù hợp với thứ tự này. Vì biết rằng có thể có nhiều cặp giá trị phù hợp, cô muốn chọn cặp làm khối lượng nguyên tử của Codium nhỏ nhất. Nếu có nhiều cặp cùng đạt khối lượng nguyên tử nhỏ nhất của Codium, cô muốn chọn cặp có khối lượng nguyên tử của Jamarium nhỏ nhất.

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. 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 biểu thị số nguyên tử Codium và Jamarium trong phân tử thứ \(i\). Các phân tử được cho theo thứ tự khối lượng phân tử tăng nghiêm ngặt.

Dữ liệu ra

Với mỗi bộ test, in 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), còn y là IMPOSSIBLE (viết hoa) nếu không có cặp khối lượng nguyên tử nguyên nào làm cho khối lượng phân tử tăng nghiêm ngặt theo thứ tự đã cho. Nếu có, y phải là hai số nguyên c j, trong đó c là khối lượng nguyên tử của Codium và j là khối lượng nguyên tử của Jamarium, được chọn theo các quy tắc ở trên.

Ràng buộc

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

Phân nhóm

Test Set 1 (Công khai)

• \(1 \le C_i \le 100\) với mọi \(i\).
• \(1 \le J_i \le 100\) với mọi \(i\).

Test Set 2 (Ẩn)

• \(1 \le C_i \le 10^9\) với mọi \(i\).
• \(1 \le J_i \le 10^9\) với mọi \(i\).

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

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

Nguồn

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

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