No.3166 [Cherry 7th Tune *] Guardians of the Cherry Tree
Problem Visual
▶ Open to reveal the problem visual
Problem Statement
$N$ guardians (Mamoribito) are on a circular road of length $L$ around a certain $1$ cherry tree. There is exactly $1$ base on the road.
The $i$-th guardian stands at the point reached by moving $X_i$ counterclockwise along the circular road from the base.
Each guardian has a non-negative real parameter called toughness. A guardian whose toughness is $p$ can guard the points reachable from their standing position by traveling a distance of at most $p$ along the circular road (endpoints included).
We say that "the cherry tree is perfectly guarded" if and only if the following holds.
- For every point on the circular road, there are at least $K$ guardians who can guard that point.
Let $\widetilde{P}$ be the minimum value of $P$ satisfying the following condition.
- When the toughness of all $N$ guardians is $P$, the cherry tree is perfectly guarded.
Find the ceiling $\left \lceil \widetilde{P} \right \rceil$ of $\widetilde{P}$.
Solve $T$ test cases.
Constraints
- $1 \leq T \leq 10^4$.
- Constraints for each test case:
- $1 \leq N \leq 2 \times 10^4$.
- $1 \leq L \leq 10^9$.
- $1 \leq K \leq N$.
- $0 \leq X_i < L \quad (1 \leq i \leq N)$.
- Constraints for each test file:
- The sum of $N$ over the $T$ test cases is at most $2 \times 10^4$.
- All input values are integers.
Input
The input is given from standard input. The $1$-st line of the input and those following it are as below.$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$
Each test case is given in the following format.
$N$ $L$ $K$ $X_1$ $X_2$ $\dots$ $X_N$
Output
The output consists of $T$ lines. On the $t~(1 \leq t \leq T)$-th line, print the answer to the $t$-th test case as an integer.
Sample
Sample 1
Input
3 3 11 2 0 2 5 10 400 5 0 0 139 100 200 74 384 100 248 41 1 46 1 0
Output
5 150 23
- [Test case $1$] $\widetilde{P} = 4.5$. Indeed, when the toughness of all $3$ guardians is $4.5$, the points each guardian can guard are as follows.
Here, the point reached by moving $x$ counterclockwise along the circular road from the base is called coordinate $x$, the set of points with coordinates at least $l$ and at most $r$ is written as $[l,r]$, and the interval of coordinates at least $l$ and less than $r$ is written as $[l,r)$.
- Guardian $1$: $[0, 4.5]$ and $[6.5, 11)$.
- Guardian $2$: $[0, 6.5]$ and $[8.5, 11)$.
- Guardian $3$: $[0.5, 9.5]$
Sample 2
Input
1 11 2023 7 113 109 725 707 412 217 1108 509 818 215 122
Output
958
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun