trang chủ / đề bài / icpcwf13_f

Công suất thấp

Đề bài

Mô tả

Bạn đang chế tạo những con chip tiên tiến cho các cỗ máy. Làm chip thì dễ, nhưng nguồn điện lại là vấn đề, vì các viên pin hiện có có công suất khác nhau.

Xét bài toán với n cỗ máy, mỗi máy có hai con chip, và mỗi con chip được cấp điện bởi k viên pin. Điều bất ngờ là mỗi chip nhận được bao nhiêu điện không quan trọng, nhưng một cỗ máy hoạt động tốt nhất khi công suất của hai con chip của nó càng gần nhau càng tốt. Công suất của một con chip đơn giản là công suất nhỏ nhất trong k viên pin của nó.

Bạn có một kho gồm 2nk viên pin và muốn phân chúng cho các con chip (mỗi viên pin dùng cho đúng một chip). Có thể không phân được sao cho trong mọi máy hai con chip có công suất bằng nhau, nhưng bạn muốn phân sao cho các chênh lệch càng nhỏ càng tốt. Chính xác hơn, bạn muốn nói với khách hàng rằng trong mọi cỗ máy, chênh lệch công suất giữa hai con chip không vượt quá d, và bạn muốn d nhỏ nhất có thể.

Để làm được điều này, bạn phải tìm một cách phân pin tối ưu cho các cỗ máy.

Xét ví dụ thứ nhất. Có 2 cỗ máy, mỗi chip cần 3 viên pin, và kho có các viên pin với công suất 1,2,3,4,5,6,7,8,9,10,11,12. Chẳng hạn, có thể gán các viên pin công suất 1,3,5 cho một con chip, các viên 2,4,12 cho con chip còn lại của cùng máy đó, các viên 6,8,9 cho con chip thứ ba và các viên 7,10,11 cho con chip thứ tư. Công suất của các con chip lần lượt là 1,2,6 và 7, và chênh lệch công suất trong cả hai máy đều là 1. Lưu ý còn nhiều cách khác đạt được kết quả này.

Dữ liệu vào

Dữ liệu gồm một test duy nhất, trên hai dòng:

  • Dòng đầu chứa hai số nguyên dương n và k: số cỗ máy và số viên pin của mỗi con chip.
  • Dòng thứ hai chứa 2nk số nguyên pi: công suất của các viên pin.

Dữ liệu ra

In ra số d nhỏ nhất sao cho có thể phân pin để trong mọi cỗ máy, chênh lệch công suất giữa hai con chip không vượt quá d.

Ràng buộc

  • n≥1, k≥1, 2nk≤106.
  • 1≤pi≤109.

Ví dụ

Input Output Giải thích
2 3
1 2 3 4 5 6 7 8 9 10 11 12
1 Cách phân như trong đề: các chip {1,3,5}, {2,4,12} ở máy thứ nhất (công suất 1 và 2), {6,8,9}, {7,10,11} ở máy thứ hai (công suất 6 và 7). Không thể đạt d=0 vì mọi công suất đều khác nhau.
2 2
3 1 3 3 3 3 3 3
2 Chip chứa viên pin công suất 1 có công suất 1, mọi chip khác có công suất 3, nên máy chứa chip đó có chênh lệch 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