MINI CANDY

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

An và Bình là hai anh em.


Ba của An sau một chuyến đi công tác xa nhà trở về, mua cho An và Bình \(N\) gói kẹo, gói thứ \(i\) có \(A_i\) viên kẹo.


Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:


- Trước hết, ba của An chọn ra một số nguyên \(k\) (với \(1 \leq k \leq N\))


- An sẽ được chia các gói kẹo từ \(1\) đến \(k\). Phần còn lại (các gói kẹo từ \(k + 1\) đến \(N\)) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số \(k\) sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Input

  • Dòng đầu tiên gồm số nguyên \(N (2 \leq N \leq 200000)\) - số gói kẹo.
  • Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N (1 \leq A_i \leq 10^9)\) - số viên kẹo trong từng gói kẹo.

Output

  • In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N \le 2000\).
  • Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input 
5
5 1 3 2 6
Output 
1
Note

Trong ví dụ thứ nhất, nếu chọn \(k = 3\) thì tổng số kẹo An được chia là \(5 + 1 + 3 = 9\), tổng số kẹo Bình được chia là \(2 + 6 = 8\), chênh lệch lượng kẹo là \(|9 − 8| = 1\).

Test 2

Input 
6
4 5 3 6 1 2
Output 
3
Note

Trong ví dụ thứ hai, có hai cách chọn k tối ưu:
– Chọn \(k = 2\). Tổng số kẹo An được chia là \(4 + 5 = 9\), tổng số kẹo Bình được chia là \(3 + 6 + 1 + 2 = 12\), chênh lệch lượng kẹo là \(|9 − 12| = 3\).
– Chọn \(k = 3\). Tổng số kẹo An được chia là \(4 + 5 + 3 = 12\), tổng số kẹo Bình được chia là \(6 + 1 + 2 = 9\), chênh lệch lượng kẹo là \(|12 − 9| = 3\).

Test 3

Input 
2
100 100
Output 
0

Nguồn: Free Contest

Bình luận


  • 0
    trandinhnhat08072010    4:56 p.m. 12 Tháng 10, 2024

    chặt nhị phân như thế nào ạ 🙂


    • 7
      tk22NguyenMinhPhuc    10:14 p.m. 16 Tháng 9, 2023 ← chỉnh sửa 2

      quá dễ


      • 0
        UserName    8:17 a.m. 6 Tháng 6, 2023

        ad mở lại test đi ạ

        1 phản hồi

        • 3
          khanhhunghack    6:46 p.m. 19 Tháng 12, 2021

          || Hint
          Spoil: dành cho Scratch.
          Tách số và chặt nhị phân
          ||


          • 0
            LeNam2021    12:12 p.m. 27 Tháng 11, 2021

            N=200000, số có 9 chữ số cộng khoảng trắng là 10. Scratch mất 2.000.000 lần lặp. Cộng mảng tổng dồn thành ra mất 2.200.000 lần xử lý cho lấy số và mảng tổng dồn.

            1 phản hồi

            • 0
              LeNam2021    8:33 a.m. 27 Tháng 11, 2021

              Với N>=100.000. Time Limit không đủ cho Scratch. Scratch tách chuỗi lấy số rất chậm.

              1 phản hồi