#393. BTNUGA - Những gói kẹo Nuga huyền thoại

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài
Đưa lên bởi: Chùm CUỐI

Đề bài

Trung thu năm nay Tí và Tèo được chị Hằng tặng cho rất nhiều kẹo Nuga, Tí và Tèo muốn chia số kẹo này sao cho chênh lệch số kẹo giữa hai người là nhỏ nhất với điều kiện là giữ nguyên các gói kẹo. Em hãy giúp hai bạn chia kẹo nhé.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương N là số gói kẹo;
  • Dòng thứ hai chứa N số nguyên dương k_1, k_2, …, k_N là số lượng kẹo của mỗi gói, mỗi số cách nhau bởi một dấu cách.

Dữ liệu ra:

  • Gồm một dòng, liệt kê số lượng kẹo của các gói kẹo mà Tí nhận được (tất nhiên những gói kẹo không liệt kê ra sẽ thuộc về Tèo), mỗi số cách nhau một dấu cách. (chỉ cần liệt kê một cách chia)

Ví dụ:

Dữ liệu vào:
5
10 20 20 30 15
Dữ liệu ra:
20 30
Giải thích:
  • Cách chia tốt nhất là chênh lệch số kẹo giữa hai bạn là 5 (một bạn được 50 cái và một bạn được 45 cái).

Giới hạn:

  • 1 ≤ n ≤ 20, 1 ≤ k_i ≤ 10^9