trang chủ / đề bài / icpcwf14_g

Nhà máy chế biến kim loại

Đề bài

Mô tả

Yulia làm việc tại một nhà máy chế biến kim loại ở Ekaterinburg. Nhà máy này chế biến quặng khai thác từ dãy núi Ural, tách ra các kim loại quý như chalcopyrit, bạch kim và vàng từ quặng.

Mỗi tháng nhà máy nhận n lô quặng thô. Yulia cần chia các lô này thành hai nhóm dựa trên mức độ giống nhau của chúng. Sau đó, mỗi nhóm được gửi tới một trong hai phân xưởng chế biến quặng của nhà máy.

Để chia nhóm, trước hết Yulia tính một khoảng cách d(i,j) cho mỗi cặp lô 1≤i≤n và 1≤j≤n, khoảng cách càng nhỏ thì hai lô i và j càng giống nhau. Với một tập con S⊆{1,…,n} các lô, cô định nghĩa độ chênh lệch D của S là khoảng cách lớn nhất giữa hai lô trong tập con đó, tức là

D(S)=maxi,j∈Sd(i,j).

Sau đó Yulia chia các lô thành hai tập con A và B sao cho tổng độ chênh lệch D(A)+D(B) là nhỏ nhất. Nhiệm vụ của bạn là giúp cô tìm cách chia này.

Dữ liệu vào

Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa số nguyên n, số lô quặng. n−1 dòng tiếp theo chứa các khoảng cách d(i,j). Dòng thứ i trong số đó chứa n−i số nguyên, số nguyên thứ j của dòng là giá trị d(i,i+j). Các khoảng cách đối xứng, tức là d(j,i)=d(i,j), và khoảng cách từ một lô tới chính nó bằng 0.

Dữ liệu ra

In ra tổng độ chênh lệch nhỏ nhất có thể khi chia các lô thành hai nhóm.

Ràng buộc

  • 1≤n≤200.
  • Mọi khoảng cách là số nguyên trong đoạn [0,109].

Ví dụ

Input Output Giải thích
5
4 5 0 2
1 3 7
2 0
4
4 Chọn A={1,2,4} và B={3,5}: D(A)=max(d(1,2),d(1,4),d(2,4))=max(4,0,3)=4 và D(B)=d(3,5)=0, tổng 4.
7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3
15 Chọn A={1,2,4,5} và B={3,6,7}: D(A)=d(2,4)=10 và D(B)=5, tổng 15.

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