Dãy con dài nhất có tổng đối xứng
Xem dạng PDF
Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Một dãy các số nguyên không âm ~A[1], A[2], …, A[N]~ được gọi là dãy tổng đối xứng nếu ta có thể tách dãy đó làm 2 dãy có tổng các giá trị bằng nhau. Nghĩa là tồn tại một số k trong đoạn [1..N] sao cho tổng ~A[1] + A[2] + ... + A[k] = A[k+1] + A[k+2] + ... + A[N]~.
Yêu cầu: Cho một dãy gồm ~N~ số nguyên không âm. Hãy tìm dãy con gồm các phần tử liên tiếp dài nhất mà cũng là dãy tổng đối xứng.
Input:
- Dòng đầu tiên chứa số nguyên N ~(2 \le N \le 5000)~.
- Dòng 2: chứa ~N~ phần tử ~A[i]~ của dãy ( ~i = 1, 2, …, N~). Các số trong dãy không âm và nhỏ hơn ~200000~
Output:
- Gồm một dòng: Ghi 1 số là độ dài lớn nhất của dãy con gồm các phần tử liên tiếp dài nhất là dãy tổng đối xứng. Nếu không có kết quả thì ghi số 0.
Example:
Input:
6
2 10 3 2 5 1
Output:
4
Bình luận
(┬┬﹏┬┬)(┬┬﹏┬┬)
khó thế