Dãy số

Xem dạng PDF
Gửi bài giải
Điểm: 0,10 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
VNOI Marathon '08 - Practice RoundSource: Russian Winter Training Camp 2004
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy số nguyên a1, a2, ..., an (~1 \leq n \leq 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~ + ... + ~a_{j─2}~ ~>~ 0
  • ~a_{j}~ + ~a_{j+1}~ + ... + ~a_{n}~ + ~a_1~ + ~a_2~ + ... + ~a_{j─2}~ + ~a_{j─1}~ ~>~ 0

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

Input

  • Dòng đầu tiên chứa số nguyên n.
  • Dòng thứ 2 chứa dãy số ~a_1~, ~a_2~,...,~a_{n}~.

Output

  • In ra 1 số nguyên duy nhất là số vị trí tốt.

Sample Input

5
0 1 -2 10 3

Sample Output

2

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 6
    kuriyama_san  đã bình luận lúc 15, Tháng 10, 2024, 17:24 ← chỉnh sửa

    Bạn nào dùng Segment Tree + prefixSum nhưng cứ bị sai test 2, 11, 15, 16, 18, 19, 20, 21 thì là do Segment Tree của bạn khởi tạo bị thiếu phần tử nhé. Do mảng A cũng như mảng PrefixSum độ dài 2 * MaxN. Vậy Segment Tree phải có độ dài 4 * 2 * MaxN mới đủ chứa mảng F


  • 17
    hieuhfgr  đã bình luận lúc 17, Tháng 6, 2024, 6:44 ← chỉnh sửa

    Hint

    kéo độ dài mảng ~n~ phần tử ra thành ~2*n~ phần tử. Giả sử có mảng ~pre_i~ ~(1 \le i \le 2*n)~, khi xét dãy con độ dài ~n~ trong dãy ~pre~ thì có tính chất gì?

    Solution:

    kéo dài mảng ~a~ thành mảng độ dài ~2*n~ bằng cách gán ~a[n+i] = a[i]~. Gọi ~pre_i~ là tổng tiền tố từ 1 đến ~i~. Ta cho ~i~ chạy từ ~1->n~ và xét mảng dãy có độ dài ~n~ bắt đầu từ ~i~:

    • Để thỏa mãn điều kiện thì cần không tồn tài một vị trí ~j~ ~(i \le j \le i+n-1)~ mà ~pre_j-pre_i \le 0~
    • đến bước này thì ta có thể xài segment tri để lấy ~val = min(pre[i], pre[i+1], pre[i+2],...,pre[i+n-1])~ và kiểm tra xem ~val-pre[i-1] > 0~ hay không

    lần đầu viết sol mong mọi ng đừng downvote T_T


    • -7
      hieuz08  đã bình luận lúc 17, Tháng 10, 2024, 15:10

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -7
      kakacoder  đã bình luận lúc 20, Tháng 6, 2024, 14:28

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    hienduy  đã bình luận lúc 27, Tháng 2, 2024, 8:36

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -40
    hathaictb  đã bình luận lúc 22, Tháng 6, 2021, 10:11

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -24
      nictysine1  đã bình luận lúc 28, Tháng 2, 2022, 8:59

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.