Bài toán 1: Bài toán chia kẹo

Phát biểu bài toán

Cho n gói kẹo, gói thứ i có a_i viên.

Hãy chia các gói kẹo thành 2 phần sao cho độ chênh lệch tổng số viên kẹo giữa hai phần là nhỏ nhất.

Dữ liệu vào

Đọc từ file văn bản CHIAKEO.INP:

• Dòng 1 ghi số nguyên dương n (1 ≤ n ≤ 10^5)
• Dòng 2 ghi n số nguyên dương a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^5)

Dữ liệu ra

Ghi ra file văn bản CHIAKEO.OUT:

• Một số nguyên duy nhất là độ chênh lệch nhỏ nhất giữa hai phần.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 1 ≤ a_i ≤ 10^5

Chấm điểm

• Subtask 1 (25 điểm): 1 ≤ n ≤ 20
• Subtask 2 (35 điểm): 1 ≤ n ≤ 1000
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm

Ví dụ

CHIAKEO.INP

5
2 4 6 8 10

CHIAKEO.OUT

2

Giải thích

Có thể chia thành hai phần:

• Phần 1: 10 + 4 = 14
• Phần 2: 8 + 6 + 2 = 16

Độ chênh lệch là |14 - 16| = 2, đây là giá trị nhỏ nhất.

Gợi ý

Gọi S là tổng số viên kẹo của tất cả các gói.

Nếu chọn một nhóm có tổng là x, thì nhóm còn lại có tổng là S - x.

Độ chênh lệch giữa hai nhóm là:

|S - 2 * x|

Vì vậy cần tìm một tổng x sao cho giá trị trên là nhỏ nhất.