TLEOJ Contest #14 - Absolute Force

View as PDF

Submit solution

Points: 800
Time limit: 1.0s
Memory limit: 256M
Input: ABSF.inp
Output: ABSF.out

Author:
Problem type
Allowed languages
C++, Pascal, pypy, pypy3, Python

\text{In physics, specifically in electromagnetism, the Lorentz force (or electromagnetic force) is the combination of electric and magnetic force on a point charge due to electro-}
Nah, too complicated. We don't do electromagnetism here. Let us call our version of Lorentz force \text{Absolute Force}.

Bạn có n vị trí trên trục \text{Ox}, điểm thứ i có khoảng cách so với điểm 0 một khoảng x_i, và không hai vị trí nào trùng nhau. Bạn được cho một số m, hãy đặt m điện tích vào các vị trí đã cho, sao cho lực điện \text{Absolute Force} tạo ra từ m điện tích được đặt ở các vị trí bất kì được đánh dấu sẵn là lớn nhất.

Lực điện \text{Absolute Force} giữa hai điện tích ở hai vị trí lần lượt là x_1, x_2 được tính đơn giản bằng |x_1 - x_2|.

Lực điện \text{Absolute Force} của m điện tích lấy độ lớn lực điện \text{Absolute Force} nhỏ nhất giữa hai điện tích bất kì trong m điện tích cho trước làm giá trị của nó.

Giả dụ, với ba điện tích nằm ở ba điểm x = 2, x = 3, x = 5, thì lực điện \text{Absolute Force} nhận được sẽ là \text{min}(|3 - 2|, |5 - 3|, |5 - 2|) = 1.

Hãy tìm cách đặt m điện tích sao cho lực điện \text{Absolute Force} của m điện tích cho trước lớn nhất.

\text{Input} ABSF.inp

  • Mỗi test bao gồm nhiều testcases. Dòng đầu gồm một số T (1 \le T \le 10^4), thể hiện số lượng testcases. Dưới đây là dữ liệu của T testcases, mỗi testcase có cấu trúc được trình bày như dưới đây.
  • Dòng đầu của mỗi testcase có hai số n (2 \le n \le 5*10^4) - thể hiện số điểm được đánh dấu trên trục \text{Ox}, và m (2 \le m \le n) - thể hiện số lượng điện tích cần đặt vào vị trí được đánh dấu trên trục \text{Ox}.
  • Dòng thứ hai của mỗi testcase có n số, số thứ i có giá trị là x_i (1 \le x_i \le 10^{18}), thể hiện vị trí được đánh dấu trên trục \text{Ox}. \text{Input} được đảm bảo rằng các giá trị x_i trong mỗi testcase khác nhau đôi một.
  • Một điều kiện bổ sung cho \text{Input} là tổng các giá trị n trong các testcases không vượt quá 5*10^4.

\text{Output} ABSF.out

  • Với mỗi testcase, in ra một giá trị duy nhất là độ lớn lớn nhất có thể của lực điện \text{Absolute Force} của m điện tích cho trước.

\text{Scoring}

  • Subtask \text{#}1 (30\% số điểm): T = 10^4.
  • Subtask \text{#}2 (70\% số điểm): Không có điều kiện gì thêm.

\text{Examples}

\text{Test #}1

\text{Input}

2
2 2
69 420
5 3
2 4 6 9 10

\text{Output}

351
4
\text{Explanations}

Ở testcase \text{#}1, vì n = m nên cách đặt duy nhất là đặt hai điện tích ở vị trí x = 69x = 420, và lực điện \text{Absolute Force} giữa hai điểm này là |420 - 69| = 351.
Ở testcase \text{#}2, cách đặt tốt nhất là đặt ba điện tích ở ba điểm x = 2, x = 6, và x = 10. Lúc này, các lực điện \text{Absolute Force} giữa các điện tích lúc đó là 4. Có thể chứng minh được không có cách đặt nào khác với lực điện \text{Absolute Force} giữa các điện tích lớn hơn 4.


Comments

There are no comments at the moment.