Chia kẹo chênh lệch nhỏ nhất
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Có $N$ gói kẹo, gói thứ $i$ có $A_i$ viên kẹo. Bạn muốn chia $N$ gói kẹo này thành hai phần (mỗi phần có thể có $0$ hoặc nhiều gói, không được tách lẻ gói) sao cho độ chênh lệch tuyệt đối giữa tổng số kẹo của hai phần là nhỏ nhất có thể.
Hãy tìm độ chênh lệch nhỏ nhất đó.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 500$).
- Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 1000$).
Dữ liệu ra
Một số nguyên duy nhất là độ chênh lệch nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
4<br>1 6 11 5 |
1 |
Giới hạn
- $1 \le N \le 500$
- $\sum A_i \le 10^5$
Community Discussion