TLEOJ Contest #14 - Absolute Force - TLEOJ: TLE Online Judge

TLEOJ Contest #14 - Absolute Force

Điểm: 800

Thời gian: 1.0s

Bộ nhớ: 256M

Input: ABSF.inp

Output: ABSF.out

Tác giả:

SolraNeubauler

Dạng bài

Ngôn ngữ cho phép

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}$

$\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 = 69$ và $x = 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$ .

Bình luận

Không có bình luận nào.