Bài 4. Chia quà (4,0 điểm; Đề HSG9 tỉnh Bắc Giang 2024-2025)

Bố của hai anh em Bắc và Giang vừa có một chuyến đi công tác về. Ông đã chuẩn bị N gói quà, các gói quà được đánh số từ 1 đến N, gói quà thứ i có giá trị là a_i. Ông sẽ chia hết số quà cho hai anh em Bắc và Giang vì hai anh em đã động viên ông trong suốt quãng thời gian ông đi công tác. Ông chia quà thành hai phần với tổng giá trị của từng phần là S1 và S2, độ chênh lệch giữa hai phần quà là |S1-S2| và mỗi anh em sẽ nhận một trong hai phần quà đó.
Trước khi chia quà cho các con, ông đã ghi lần lượt các số 1 và 2 trên các gói quà, lúc chia nếu gói quà ghi số 1 thì ông chia cho Bắc, gói quà ghi số 2 ông chia cho Giang. Như vậy, độ chênh lệch của hai phần quà đã được xác định. Ông đã suy nghĩ và muốn chia quà cho các con để sao cho độ chênh lệch giữa hai phần quà là nhỏ nhất.
Yêu cầu: Hãy giúp bố của Bắc và Giang chia quà cho hai anh em sao cho độ chênh lệch giữa hai phần quà là nhỏ nhất.
Dữ liệu: Vào từ tệp văn bản BAI4.INP gồm:

• Dòng 1 ghi số nguyên dương N;
• Dòng 2 ghi N số a₁, a₂, ... a_N (1 ≤ a_i ≤ 10000, i = 1..N);
• Dòng 3 ghi dãy gồm N số (số 1 hoặc số 2) tương ứng với cách chia quà ban đầu của bố Bắc và Giang (số thứ i bằng 1 thì ông chia gói quà thứ i cho Bắc, số thứ i bằng 2 thì ông chia gói quà thứ i cho Giang).

Kết quả: Ghi ra tệp văn bản BAI4.OUT gồm:

• Dòng 1 ghi độ chênh lệch của cách chia ban đầu;
• Dòng 2 ghi độ chênh lệch nhỏ nhất tìm được.

Ví dụ:

Giới hạn:

• Subtask 1: có 30 test (75%) tương ứng 3,0 điểm với 1 ≤ N ≤ 20;
• Subtask 2: có 10 test (25%) tương ứng 1,0 điểm với 20 < N ≤ 100.

Ghi chú:

• Với mỗi bộ test thí sinh đưa ra kết quả dòng một đúng được 75% điểm, kết quả dòng 2 đúng được 25% điểm của bộ test đó.