Dãy số

View as PDF
Submit solution
Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
VNOI Marathon '08 - Practice RoundSource: Russian Winter Training Camp 2004
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 3
    kuriyama_san  commented on Oct. 15, 2024, 5:24 p.m. ← edited

    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


  • 10
    hieuhfgr  commented on June 17, 2024, 6:44 a.m. ← edited

    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


    • -6
      hieuz08  commented on Oct. 17, 2024, 3:10 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • -7
      kakacoder  commented on June 20, 2024, 2:28 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    hienduy  commented on Feb. 27, 2024, 8:36 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -40
    hathaictb  commented on June 22, 2021, 10:11 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -24
      nictysine1  commented on Feb. 28, 2022, 8:59 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.