(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 ...