Tôi có một tập hợp các số nguyên dương \(S\). Bạn có thể tìm thấy hai tập hợp con khác nhau, không rỗng, có cùng tổng hay không?

Lưu ý: Một tập hợp con là một tập hợp chỉ chứa các phần tử từ \(S\), và hai tập hợp con là khác nhau nếu chúng không có chính xác các phần tử giống nhau.

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ộ trên một dòng. Mỗi bộ test bắt đầu bằng \(N\), số lượng số nguyên dương trong \(S\). Tiếp theo là \(N\) số nguyên dương phân biệt, tất cả nằm trên cùng một dòng.

Dữ liệu ra

Đối với mỗi bộ test, trước tiên hãy in ra một dòng chứa "Case #x:", trong đó x là số thứ tự bộ test (bắt đầu từ 1).

• Nếu có hai tập hợp con khác nhau của \(S\) có cùng tổng, hãy in ra các tập hợp con này, mỗi tập hợp trên một dòng. Mỗi dòng nên chứa các số trong một tập hợp con, cách nhau bởi dấu cách.
• Nếu không thể, bạn nên in ra chuỗi "Impossible" trên một dòng duy nhất.

Nếu có nhiều cách chọn hai tập hợp con có cùng tổng, bất kỳ lựa chọn nào cũng được chấp nhận.

Ràng buộc

• Không có hai số nào trong \(S\) bằng nhau.
• \(1 \le T \le 10\).

Phân nhóm

Test set 1 (Visible Verdict)

• \(N\) chính xác bằng 20.
• Mỗi số trong \(S\) sẽ là một số nguyên dương nhỏ hơn \(10^5\).

Test set 2 (Hidden Verdict)

• \(N\) chính xác bằng 500.
• Mỗi số trong \(S\) sẽ là một số nguyên dương nhỏ hơn \(10^{12}\).

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

2
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 120 266 858 1243 1657 1771 2328 2490 2665 2894 3117 4210 4454 4943 5690 6170 7048 7125 9512 9600

Case #1: Possible
Case #2: Possible

Nguồn

Google Code Jam 2012, Vòng 1B, bài Equal Sums.

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