Vị trí tốt

Xem PDF

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho dãy số nguyên \(a_1, a_2, ..., a_n\) (\(1<=n<=100000\)), mỗi số không vượt quá 10000. Dãy số này được viết trên một vòng tròn. Nghĩa là, khi cắt vòng tròn tại vị trí j, ta thu được:
\(a_j,a_{j+1},...,a_n,a_1,a_2, ...,a_{j-1}\)

Vị trí j được gọi là vị trí tốt, nếu các điều kiện sau đây được thỏa mãn:

  • \(a_j>0\)
  • \(a_j+a_{j+1}>0\)
  • ...
  • \(a_j+a_{j+1}+...+a_n>0\)
  • \(a_j+a_{j+1}+...+a_n+a_1>0\)
  • \(a_j+a_{j+1}+...+a_n+a_1+a_2>0\)
  • ...
  • \(a_j+a_{j+1}+...+a_n+a_1++a_2...+a_{j-1}>0\)

Yêu cầu: hãy đếm số vị trí tốt.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương \(n\).
  • Dòng thứ hai chứa dãy số \(a_1,a_2,...,a_n\).

Dữ liệu ra

  • Dòng đầu tiên ghi kết quả tìm được.
Ví dụ
Input
5
0 1 -2 10 3
Output
2
Giải thích
Là 2 vị trí 4 và 5

Bình luận

Không có bình luận nào.