trang chủ / đề bài / icpc26_mb_d

Đào xúc regolith

Đề bài

Mô tả

Một cơn bão vũ trụ đã phủ lớp regolith (đất đá vụn) nguy hiểm dọc theo một đường hào dài n. Đường hào gồm n ô được đánh số từ 1 đến n từ trái sang phải, ô i chứa zi gam regolith (1≤i≤n). Bên ngoài đường hào có hai trạm thải: trạm 0 (bên trái) và trạm n+1 (bên phải).

Tiến sĩ Aurel có 40 chiếc xẻng trọng lực được đánh số từ 0 đến 39. Xẻng k (0≤k≤39) mỗi lần có thể vận chuyển tối đa 2k gam regolith giữa hai ô kề nhau (từ ô i sang ô i−1, hoặc từ ô i sang ô i+1) với chi phí k+1 calo.

Để điều phối việc dọn dẹp, người ta chọn một ngưỡng phân chia x (1≤x<n):

  • Toàn bộ regolith ở các ô ≤x được chuyển sang trái về trạm 0.
  • Toàn bộ regolith ở các ô >x được chuyển sang phải về trạm n+1.

Hãy giải một trong hai bài toán con, tùy theo C:

  • Nếu C=1: cho trước x, hãy tính tổng số calo nhỏ nhất cần dùng.
  • Nếu C=2: hãy tìm giá trị x (1≤x<n) sao cho tổng số calo tiêu tốn là nhỏ nhất. Nếu có nhiều giá trị x cùng đạt giá trị nhỏ nhất, hãy tìm x nhỏ nhất.

Dữ liệu vào

  • Dòng 1: số nguyên C∈{1,2}.
  • Dòng 2: số nguyên n (2≤n≤105).
  • Dòng 3: n số nguyên z1,z2,…,zn cách nhau bởi dấu cách (1≤zi≤106).
  • Dòng 4 (chỉ có khi C=1): số nguyên x (1≤x<n).

Dữ liệu ra

In ra một số nguyên duy nhất: đáp án của bài toán con C.

Ràng buộc

  • C∈{1,2}.
  • 2≤n≤105.
  • 1≤zi≤106.
  • 1≤x<n (khi C=1).

Ví dụ

Input Output Giải thích
1
4
1 3 1 3
2
10 Ô 1,2 chuyển về trạm 0: từ ô 2 sang ô 1 chuyển 3 gam (xẻng 1 và xẻng 0, hoặc một lần xẻng 2: 3 calo), từ ô 1 sang trạm 0 chuyển 4 gam (xẻng 2: 3 calo). Ô 3,4 chuyển về trạm 5: từ ô 3 sang ô 4 chuyển 1 gam (1 calo), từ ô 4 sang trạm 5 chuyển 4 gam (3 calo). Tổng 3+3+1+3=10.
2
5
2 1 1 1 2
2 Ví dụ bổ sung (không có trong đề gốc). Tổng calo nhỏ nhất với x=1,2,3,4 lần lượt là 12,10,10,12; cả x=2 và x=3 đều tối ưu nên in x nhỏ hơn là 2.

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