English · Original
Chinese · Translation
Formal · Original
Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be represented as a sequence _a_1, _a_2, ..., _a__n_ of _n_ integer numbers — saturation of the color of each pencil. Now Mishka wants to put all the mess in the pack in order. He has an infinite number of empty boxes to do this. He would like to fill some boxes in such a way that:
* Each pencil belongs to **exactly** one box;
* Each non-empty box has at least _k_ pencils in it;
* If pencils _i_ and _j_ belong to the same box, then |_a__i_ - _a__j_| ≤ _d_, where |_x_| means absolute value of _x_. Note that the opposite is optional, there can be pencils _i_ and _j_ such that |_a__i_ - _a__j_| ≤ _d_ and they belong to different boxes.
Help Mishka to determine if it's possible to distribute all the pencils into boxes. Print "_YES_" if there exists such a distribution. Otherwise print "_NO_".
## Input
The first line contains three integer numbers _n_, _k_ and _d_ (1 ≤ _k_ ≤ _n_ ≤ 5·105, 0 ≤ _d_ ≤ 109) — the number of pencils, minimal size of any non-empty box and maximal difference in saturation between any pair of pencils in the same box, respectively.
The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — saturation of color of each pencil.
## Output
Print "_YES_" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "_NO_".
[samples]
## Note
In the first example it is possible to distribute pencils into 2 boxes with 3 pencils in each with any distribution. And you also can put all the pencils into the same box, difference of any pair in it won't exceed 10.
In the second example you can split pencils of saturations \[4, 5, 3, 4\] into 2 boxes of size 2 and put the remaining ones into another box.
Mishka 收到了一份多彩铅笔作为生日礼物！可惜他生活在一个单色世界中，这里的一切都是同一种颜色，只有饱和度不同。这个套装可以表示为一个包含 $n$ 个整数的序列 $[a_1, a_2, \dots, a_n]$ —— 每支铅笔的颜色饱和度。现在 Mishka 希望将包里的混乱整理有序。他拥有无限多个空盒子来完成这项工作。他希望以如下方式填充一些盒子：
帮助 Mishka 判断是否可能将所有铅笔分配到盒子中。如果存在这样的分配方式，请输出 "_YES_"；否则输出 "_NO_"。
第一行包含三个整数 $n$、$k$ 和 $d$（$1 \leq k \leq n \leq 5\cdot10^5$，$0 \leq d \leq 10^9$）—— 分别表示铅笔的数量、任意非空盒子的最小容量、以及同一盒子中任意两支铅笔饱和度的最大允许差值。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）—— 每支铅笔的饱和度。
如果可以将所有铅笔分配到盒子中并满足所有条件，则输出 "_YES_"；否则输出 "_NO_"。
在第一个例子中，可以将铅笔分配到 $2$ 个盒子中，每个盒子包含 $3$ 支铅笔，任意分配方式均可。你也可以将所有铅笔放入同一个盒子中，其中任意两支铅笔的差值不会超过 $10$。
在第二个例子中，你可以将饱和度为 $[4, 5, 3, 4]$ 的铅笔分成 $2$ 个大小为 $2$ 的盒子，并将剩余的铅笔放入另一个盒子中。
## Input
第一行包含三个整数 $n$、$k$ 和 $d$（$1 \leq k \leq n \leq 5\cdot10^5$，$0 \leq d \leq 10^9$）—— 分别表示铅笔的数量、任意非空盒子的最小容量、以及同一盒子中任意两支铅笔饱和度的最大允许差值。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）—— 每支铅笔的饱和度。
## Output
如果可以将所有铅笔分配到盒子中并满足所有条件，则输出 "_YES_"；否则输出 "_NO_"。
[samples]
## Note
在第一个例子中，可以将铅笔分配到 $2$ 个盒子中，每个盒子包含 $3$ 支铅笔，任意分配方式均可。你也可以将所有铅笔放入同一个盒子中，其中任意两支铅笔的差值不会超过 $10$。在第二个例子中，你可以将饱和度为 $[4, 5, 3, 4]$ 的铅笔分成 $2$ 个大小为 $2$ 的盒子，并将剩余的铅笔放入另一个盒子中。
Given:
- A sequence $ a = [a_1, a_2, \dots, a_n] $ of $ n $ integers (pencil saturations).
- Integers $ k $ (minimum box size) and $ d $ (maximum allowed difference within a box).
**Constraints for a valid box:**
- Each non-empty box must contain at least $ k $ pencils.
- For any box containing pencils with saturations $ \{a_{i_1}, a_{i_2}, \dots, a_{i_m}\} $, it must hold that
$$
\max\{a_{i_j}\} - \min\{a_{i_j}\} \leq d.
$$
**Objective:**
Determine whether there exists a partition of the multiset $ \{a_1, a_2, \dots, a_n\} $ into disjoint non-empty subsets (boxes), each satisfying the above constraints.
---
**Formal Statement:**
Let $ a = [a_1, a_2, \dots, a_n] \in \mathbb{Z}^n $, with $ 1 \leq a_i \leq 10^9 $.
Let $ k \in \mathbb{Z}^+ $, $ 1 \leq k \leq n $, and $ d \in \mathbb{Z}_{\geq 0} $.
Define a *valid box* as a non-empty subset $ S \subseteq \{a_1, \dots, a_n\} $ such that:
- $ |S| \geq k $,
- $ \max(S) - \min(S) \leq d $.
**Question:**
Does there exist a partition $ \mathcal{P} = \{S_1, S_2, \dots, S_m\} $ of the multiset $ \{a_1, \dots, a_n\} $, such that each $ S_i $ is a valid box?
**Output:**
- "YES" if such a partition exists.
- "NO" otherwise.
API Response (JSON)
{
"problem": {
"name": "E. Pencils and Boxes",
"description": {
"content": "Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be repre",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF985E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be repre...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Mishka 收到了一份多彩铅笔作为生日礼物！可惜他生活在一个单色世界中，这里的一切都是同一种颜色，只有饱和度不同。这个套装可以表示为一个包含 $n$ 个整数的序列 $[a_1, a_2, \\dots, a_n]$ —— 每支铅笔的颜色饱和度。现在 Mishka 希望将包里的混乱整理有序。他拥有无限多个空盒子来完成这项工作。他希望以如下方式填充一些盒子：\n\n帮助 Mishka 判断是否可能将所有铅...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Given: \n- A sequence $ a = [a_1, a_2, \\dots, a_n] $ of $ n $ integers (pencil saturations). \n- Integers $ k $ (minimum box size) and $ d $ (maximum allowed difference within a box). \n\n**Constraints...",
"is_translate": false,
"language": "Formal"
}
]
}