問題一覧 > 通常問題

No.3166 [Cherry 7th Tune *] Guardians of the Cherry Tree

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 52
作問者 : 👑 Kazun / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10232 / 自分の提出
問題文最終更新日: 2025-05-20 00:18:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 468 Desire for Approval ~Ash blown by the draft leads to the door to a new beginning~ (順位表) の他の問題:

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]$
    For example, coordinate $6$ is guarded by $2$ guardians: guardian $2$ and guardian $3$. Since $\left \lceil \widetilde{P} \right \rceil = 5$, the correct answer is $5$.

Sample 2
Input
1
11 2023 7
113 109 725 707 412 217 1108 509 818 215 122
Output
958

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。