(3,5 ĐIỂM) CHIA KẸO CANDY.PASCÓ N GÓI KẸO ĐƯỢC ĐÁNH CHỈ SỐ TỪ 1 ĐẾN N...
Câu 3: (3,5 điểm) Chia kẹo
CANDY.PAS
Có N gói kẹo được đánh chỉ số từ 1 đến N, gói kẹo thứ i có a
i
cái kẹo.
(1 ≤ N ≤ 1000, 1 ≤ i ≤ N, 1 ≤ a
i
≤ 32000)
Yêu cầu: Hãy tìm cách chia các gói kẹo thành hai phần sao cho độ chênh lệch giữa số
kẹo của hai phần đó là ít nhất có thể được.
Dữ liệu vào: Ghi trong file văn bản CANDY.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N.
- Dòng 2: Ghi N số nguyên dương, số thứ i tương ứng là số kẹo trong gói kẹo
thứ i. Các số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản CANDY.OUT theo cấu trúc:
- Dòng 1: Ghi 3 số nguyên dương lần lượt là tổng số kẹo ở phần 1, phần 2 và
độ chênh lệch giữa hai phần. Các số được ghi cách nhau một dấu cách.
- Dòng 2: Ghi chỉ số các gói kẹo được chia ở phần 1, các chỉ số được ghi cách
nhau một dấu cách.
- Dòng 3: Ghi chỉ số các gói kẹo được chia ở phần 2, các chỉ số được ghi cách
Ví dụ:
CANDY.INP
CANDY.OUT
4
14 12 2
3 12 4 7
1 3 4
2
(Có 55% số test với N ≤ 100; 45% số test với N >100).
... Hết ...