Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho một băng số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~, mỗi số được viết trên một ô. Hãy cắt băng số này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn là bằng nhau.

Dữ liệu vào

• Dòng đầu ghi ~n~ ~(n \le 1000)~.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ ghi một số nguyên dương ~a_i~ ~(1 \le a_i \le 1000)~.

Kết quả

• Là số lượng đoạn nhiều nhất chia được.

Giới hạn

• ~1 \le n \le 1000~; ~1 \le a_i \le 1000~.
• Các đoạn phải liên tiếp và phủ kín cả băng số (để nguyên cả băng được tính là 1 đoạn).

Sample Input 1

8
10
2
6
2
5
2
1
2

Sample Output 1

3

Giải thích

Đoạn 1: ~10~. Đoạn 2: ~2 + 6 + 2 = 10~. Đoạn 3: ~5 + 2 + 1 + 2 = 10~.