trang chủ / đề bài / icpc25_mn_k

Thử thách cân bằng mảng của Emma

Đề bài

Mô tả

Emma là chuyên viên phân tích dữ liệu của một công ty khởi nghiệp chuyên tạo các bộ dữ liệu cân bằng cho các ứng dụng học máy. Công ty của cô đã phát triển một thuật toán mang tính cách mạng, đòi hỏi các mảng số phải được cân bằng hoàn hảo để hoạt động tối ưu.

Emma có một mảng [a0,a1,a2,…,an−1] gồm n phần tử (n chẵn), biểu diễn dữ liệu cảm biến quan trọng từ các thiết bị IoT. Một mảng được gọi là cân bằng nếu tổng các phần tử ở nửa trái bằng tổng các phần tử ở nửa phải.

Ví dụ:

  • Mảng cân bằng: [1,2,5,2,4,2] có tổng nửa trái =1+2+5=8 và tổng nửa phải =2+4+2=8.
  • Mảng không cân bằng: [1,2,1,2,1,3] có tổng nửa trái =1+2+1=4 và tổng nửa phải =2+1+3=6.

Đáng tiếc là dữ liệu cảm biến thô hiếm khi cân bằng. Emma phát hiện ra rằng cô có thể sửa một mảng không cân bằng bằng cách cộng thêm các giá trị không âm vào các phần tử của mảng. Tuy nhiên, công ty muốn hạn chế tối đa việc sửa đổi dữ liệu để giữ được tính toàn vẹn của dữ liệu gốc.

Để cân bằng mảng, Emma được tăng đúng một phần tử ai thêm một số nguyên không âm x. Hãy giúp Emma tìm giá trị x nhỏ nhất làm cho mảng cân bằng.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên chẵn n.
  • Dòng thứ hai chứa n số nguyên a0,a1,a2,…,an−1.

Dữ liệu ra

In ra giá trị nhỏ nhất của x trên một dòng.

Ràng buộc

  • 1≤n≤100000, n chẵn
  • 0≤ai≤1000

Ví dụ

Input Output Giải thích
6
1 2 1 2 1 3
2 Cộng 2 vào a2: mảng [1,2,3,2,1,3] có tổng nửa trái =1+2+3=6 và tổng nửa phải =2+1+3=6.
2
7 3
4 Ví dụ bổ sung (không có trong đề gốc): cộng 4 vào a1 để được [7,7].

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0