Bạn được cho một tập các số nguyên phân biệt. Bạn cần chia chúng thành hai tập con không rỗng sao cho mỗi phần tử thuộc đúng một tập con và tổng các phần tử của hai tập con bằng nhau.

Một nguồn tin nặc danh cho biết bài toán trên khó có khả năng được giải trong thời gian đa thức (hoặc đại loại như vậy), nên chúng tôi quyết định thay đổi nó. Bây giờ bạn được quyền quyết định một nửa số nguyên!

Đây là bài tương tác gồm ba giai đoạn. Ở giai đoạn 1, bạn chọn \(\mathbf{N}\) số nguyên phân biệt. Ở giai đoạn 2, bạn nhận thêm \(\mathbf{N}\) số nguyên khác, đôi một phân biệt và cũng khác tất cả các số bạn đã chọn ở giai đoạn 1. Ở giai đoạn 3, bạn phải chia \(2\mathbf{N}\) số nguyên đó thành hai tập con có tổng bằng nhau. Cả \(2\mathbf{N}\) số nguyên đều nằm trong đoạn từ \(1\) đến \(10^9\), kể cả hai đầu, và tổng của chúng được bảo đảm là số chẵn.

Dữ liệu vào

Ban đầu, chương trình phải đọc một dòng chứa số nguyên \(\mathbf{T}\), là số lượng bộ test. Sau đó phải xử lý đủ \(\mathbf{T}\) bộ test.

Với mỗi bộ test, trước tiên chương trình phải đọc một dòng chứa số nguyên duy nhất \(\mathbf{N}\).

Dữ liệu ra

Sau khi đọc \(\mathbf{N}\), chương trình phải in một dòng chứa \(\mathbf{N}\) số nguyên phân biệt \(A_1,A_2,\ldots,A_\mathbf{N}\). Mỗi số phải nằm trong đoạn \([1,10^9]\).

Sau khi nhận dãy của giám khảo, chương trình phải in một dòng chứa từ \(1\) đến \(2\mathbf{N}-1\) số được chọn từ \(A_1,A_2,\ldots,A_\mathbf{N},\mathbf{B}_1,\mathbf{B}_2,\ldots,\mathbf{B}_\mathbf{N}\). Đây là các số thuộc tập con thứ nhất; những số trong \(A\) và \(\mathbf{B}\) không được in ra được xem là thuộc tập con còn lại.

Giao thức tương tác

Đây là bài tương tác. Bạn cần đọc kỹ phần Interactive Problems trong FAQ của Google Code Jam.

Sau khi bạn in dãy \(A\), chương trình phải đọc một dòng chứa thêm \(\mathbf{N}\) số nguyên \(\mathbf{B}_1,\mathbf{B}_2,\ldots,\mathbf{B}_\mathbf{N}\) do giám khảo cung cấp. Cuối cùng, in tập con thứ nhất như đã mô tả ở phần Dữ liệu ra.

Nếu còn bộ test, bộ test tiếp theo bắt đầu ngay lập tức. Nếu đây là bộ test cuối, giám khảo không chờ thêm đầu ra và cũng không gửi thêm đầu vào. Ngoài ra, cả \(\mathbf{T}\) bộ test luôn được xử lý, bất kể đầu ra cuối cùng của chương trình ở các bộ test trước đúng hay sai.

Lưu ý: Có thể chứng minh rằng với các giới hạn của bài toán, tồn tại một dãy \(A_1,A_2,\ldots,A_\mathbf{N}\) sao cho với mọi dãy \(\mathbf{B}_1,\mathbf{B}_2,\ldots,\mathbf{B}_\mathbf{N}\), tập gồm \(2\mathbf{N}\) số nguyên thu được đều có thể chia thành hai tập con có tổng bằng nhau.

Nếu ở bất kỳ thời điểm nào giám khảo nhận được từ chương trình một dòng sai định dạng hoặc không hợp lệ — chẳng hạn in sai số lượng số nguyên, in số ngoài phạm vi, hoặc lặp số nguyên trên một dòng — giám khảo sẽ in duy nhất số \(-1\) và không in thêm gì nữa. Nếu chương trình vẫn tiếp tục chờ giám khảo sau khi nhận \(-1\), chương trình sẽ hết thời gian và nhận lỗi Time Limit Exceeded. Bạn có trách nhiệm kết thúc chương trình kịp thời để nhận Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu vượt giới hạn bộ nhớ hoặc chương trình gặp lỗi khi chạy, bạn sẽ nhận phán quyết tương ứng.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(\mathbf{N}=100\).
• \(1 \le \mathbf{B}_i \le 10^9\) với mọi \(i\).
• \(\mathbf{B}_i\ne A_j\) với mọi \(i,j\).
• \(\mathbf{B}_i\ne\mathbf{B}_j\) với mọi \(i\ne j\).
• Trong mỗi bộ test, giám khảo chọn các \(\mathbf{B}_i\) sao cho tổng của cả \(2\mathbf{N}\) số nguyên là số chẵn.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): áp dụng toàn bộ các ràng buộc trên.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử chính thức để chạy cục bộ hoặc trên nền tảng của Google Code Jam. Khi kiểm thử cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner của Google. Hãy đọc hướng dẫn trong phần chú thích của tệp đó và phần Interactive Problems trong FAQ để biết thêm chi tiết.

Hướng dẫn dành cho công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Bạn được khuyến khích bổ sung các bộ test của riêng mình. Mặc dù công cụ được thiết kế để mô phỏng hệ thống chấm, nó không phải hệ thống chấm thật và có thể hành xử khác. Nếu chương trình vượt qua công cụ nhưng thất bại trên giám khảo thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với hệ thống chấm.

Tải công cụ kiểm thử chính thức.

Ví dụ

Nguồn

Google Code Jam 2022, Vòng 1A, bài Equal Sum.

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