Dải số

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nvatuan
Dạng bài
Điểm: 150 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một số nguyên dương \(n\) và một mảng \(A\) chứa \(n\) số nguyên (có thể âm). Bạn muốn cắt một nhát cắt trên mảng đó để chia mảng đó thành hai đoạn trái và phải, sao cho cả hai đoạn đều có ít nhất một phần tử và tổng các phần tử của hai đoạn bằng nhau.

Đề bài yêu cầu đếm có bao nhiêu cách cắt thỏa mãn điều kiện trên.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 2*10^5)\)
  • Dòng thứ hai chứa \(n\) số nguyên \(A_i,\) là số thứ \(i\) của mảng \(A (|A_i| \leq 10^9)\)

Output

  • Số cách cắt mảng \(A\) cho trước, sao cho tổng của phân đoạn trái và phân đoạn phải sau khi cắt có tổng các phần tử bằng nhau.

Example

Test 1

Input 
4
1 2 2 1
Output 
1
Note

Có \(1\) cách cắt là \([1, 2]\) / \([2, 1]\)

Test 2

Input 
6
1 1 1 3 -3 3
Output 
2
Note

Có \(2\) cách cắt là:

  1. \([1, 1, 1]\) / \([3, -3, 3]\)
  2. \([1, 1, 1, 3, -3]\) / \([3]\)

Bình luận