Dải số

Xem PDF
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


  • 0
    phanhuykhang    7:59 p.m. 15 Tháng 10, 2021

    bài này test yếu quá có mấy bạn kiểm tra như này if(b[i] == b[n] / 2) mà vẫn ac


    • 0
      VoBaThongL921    4:27 p.m. 16 Tháng 10, 2021 ← chỉnh sửa 2

      • 2
        LeQuangMinh0903    7:52 p.m. 21 Tháng 10, 2021

        mình dùng 2 biến tính tổng rồi xét nếu sum2 * 2 == sum1 thì tăng biến dem lên là xong


        • 1
          vancongnam    10:19 p.m. 20 Tháng 10, 2021

          mình để điều kiện là b[i] == b[n] - b[i] khỏi phải ktra


          • 3
            phanhuykhang    5:44 p.m. 16 Tháng 10, 2021

            b[n] / 2 c++ là chia lấy nguyên bạn nhé nên phải kt b[n] chia hết cho 2 hay ko chưa. Code bạn kt rồi thì mình ko nói gì nhưng có code chưa kt nên mình nói.


            • 0
              VoBaThongL921    5:57 p.m. 16 Tháng 10, 2021

              à ok bạn, nếu không kiểm tra tổng mảng lẻ hay chẵn thì sai thật:>


            • 1
              dang7rickroll    4:30 p.m. 16 Tháng 10, 2021

              sao tôi làm mà vẫn không ac :))


              • 0
                VoBaThongL921    4:39 p.m. 16 Tháng 10, 2021 ← chỉnh sửa 2

                vòng for thứ 2 để check của ông đó, ông phải cho nó chạy đến n - 1 thôi. Tui mới nộp lại code của ông (tui sửa lại for thứ 2 chạy đến n - 1) thì ac mà. Trước tui cũng bị như này:> Vì giả sử tổng của cả mảng là 0, nếu xét đến i = n thì thấy s[i] = s[n] - s[i] = 0 nên bị sai, vì không thể cắt dãy ở cuối cùng của mảng được !


          • 3
            nvatuan    3:45 p.m. 16 Tháng 10, 2021

            Nếu \(b\) là mảng Tổng cộng dồn thì đếm từng vị trí \(i\) mà \(b[i] == b[n]/2\) chính là solution đó bạn.

            Giả sử \(b[i] = b[n]/2\),

            \(⇔ 2*b[i] = b[n] ⇔ b[i] = b[n] - b[i]\)

            Với,

            • \(b[i]\) là tổng là từ \(1\) đến \(i\)
            • \(b[n]-b[i]\) là tổng từ \(i+1\) đến \(n\)

            Vậy, \(b[i]=b[n]/2\) sẽ tương đương với yêu cầu đề bài.


            • 0
              phanhuykhang    5:45 p.m. 16 Tháng 10, 2021

              dạ anh b[n] / 2 c++ là chia lấy nguyên nên phải kt b[n] chia hết cho 2 hay ko chưa. Có code chưa kt nên e nói.


              • 1
                nvatuan    6:07 p.m. 16 Tháng 10, 2021

                OK mình thấy bài đó rồi, bộ test thiếu trường hợp tổng là số lẻ, để mình thêm vào. Cảm ơn em

          1 bình luận nữa