(6 ĐIỂM) CHIA KẸOCHO N TÚI KẸO, TÚI THỨ I CÓ AI VIÊN. HÃY CHIA CÁC TÚ...
Bài 3: (6 điểm) Chia kẹo
Cho n túi kẹo, túi thứ i có a
i
viên. Hãy chia các túi này thành hai phần sao cho số viên
kẹo chênh lệch giữa hai phần là nhỏ nhất.
Ví dụ: Cho 7 túi có số viên kẹo trong từng túi lần lượt là: 30, 25, 40, 20, 26, 30, 20.
Sau khi chia thành 2 phần để có số viên kẹo chênh lệch giữa 2 phần nhỏ
nhất ta được kết quả:
Phần thứ nhất: 30 + 25 + 40 = 95
Phần thứ hai: 20 + 26 + 30 + 20 = 96
Vậy số viên chênh lệch nhỏ nhất là: 96 – 95 = 1
Dữ liệu vào: Cho file CHIAKEO.INP gồm:
- Dòng đầu tiên chứa số n là số lượng các túi kẹo.
- n dòng tiếp theo, dòng thứ i chứa số viên của túi kẹo thứ i.
Kết quả: Ghi ra file CHIAKEO.OUT một số nguyên là số viên chênh lệch nhỏ nhất.
CHIAKEO.INP CHIAKEO.OUT
1
7
30
25
40
20
26
Ràng buộc dữ liệu: n < 100000; 0 < a
i