D. Alarm Clock

Codeforces

IDCF898D

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Every evening Vitalya sets _n_ alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer _a__i_ — number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute. Vitalya will definitely wake up if during some _m_ consecutive minutes at least _k_ alarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time. Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on. ## Input First line contains three integers _n_, _m_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 2·105, 1 ≤ _m_ ≤ 106) — number of alarm clocks, and conditions of Vitalya's waking up. Second line contains sequence of **distinct** integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) in which _a__i_ equals minute on which _i_\-th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for 106 minutes. ## Output Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long. [samples] ## Note In first example Vitalya should turn off first alarm clock which rings at minute 3. In second example Vitalya shouldn't turn off any alarm clock because there are no interval of 10 consequence minutes in which 3 alarm clocks will ring. In third example Vitalya should turn off any 6 alarm clocks.

每天晚上，Vitalya 会设置 #cf_span[n] 个闹钟以便第二天醒来。每个闹钟恰好在一分钟内响起，其特征是一个整数 #cf_span[ai] —— 表示从午夜开始经过的第 #cf_span[ai] 分钟时响起。每个闹钟在分钟开始时响起，并在整个分钟内持续响铃。如果在某段连续的 #cf_span[m] 分钟内，至少有 #cf_span[k] 个闹钟**开始**响铃，则 Vitalya 一定会醒来。请注意，Vitalya 只考虑在给定时间段内**开始**响铃的闹钟，而不考虑在该时间段之前已经开始响铃、并在该时间段内继续响铃的闹钟。 Vitalya 非常疲惫，他希望一整天都睡觉而不醒来。请找出 Vitalya 最少需要关闭多少个闹钟，才能确保他明天一整天都不会醒来。目前所有闹钟都处于开启状态。第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 106]）—— 分别表示闹钟数量以及 Vitalya 醒来的条件。第二行包含一个由 *互不相同* 整数组成的序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 106]），其中 #cf_span[ai] 表示第 #cf_span[i] 个闹钟响起的分钟数。数字给出的顺序任意。Vitalya 生活在 Berland，那里的一天持续 #cf_span[106] 分钟。请输出 Vitalya 为确保一整天不醒来所需关闭的最少闹钟数量。在第一个示例中，Vitalya 应关闭在第 #cf_span[3] 分钟响起的第一个闹钟。在第二个示例中，Vitalya 不应关闭任何闹钟，因为不存在一个长度为 #cf_span[10] 的连续分钟区间，在其中有 #cf_span[3] 个闹钟开始响铃。在第三个示例中，Vitalya 应关闭任意 #cf_span[6] 个闹钟。 ## Input 第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 106]）—— 分别表示闹钟数量以及 Vitalya 醒来的条件。第二行包含一个由 *互不相同* 整数组成的序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 106]），其中 #cf_span[ai] 表示第 #cf_span[i] 个闹钟响起的分钟数。数字给出的顺序任意。Vitalya 生活在 Berland，那里的一天持续 #cf_span[106] 分钟。 ## Output 请输出 Vitalya 为确保一整天不醒来所需关闭的最少闹钟数量。 [samples] ## Note 在第一个示例中，Vitalya 应关闭在第 #cf_span[3] 分钟响起的第一个闹钟。在第二个示例中，Vitalya 不应关闭任何闹钟，因为不存在一个长度为 #cf_span[10] 的连续分钟区间，在其中有 #cf_span[3] 个闹钟开始响铃。在第三个示例中，Vitalya 应关闭任意 #cf_span[6] 个闹钟。

**Definitions** Let $ n, m, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 2 \cdot 10^5 $, $ 1 \leq m \leq 10^6 $. Let $ A = \{a_1, a_2, \dots, a_n\} \subset \{1, 2, \dots, 10^6\} $ be a set of distinct integers representing alarm times. **Constraints** All $ a_i $ are distinct and lie in $ [1, 10^6] $. **Objective** Find the minimal number of alarms to remove from $ A $ such that for **every** interval $ [x, x + m - 1] \subseteq [1, 10^6] $, the number of alarms in $ A $ falling inside $ [x, x + m - 1] $ is **strictly less than** $ k $. Equivalently: Minimize $ |A| - |A'| $ such that $ A' \subseteq A $ and $$ \forall x \in [1, 10^6 - m + 1], \quad \left| A' \cap [x, x + m - 1] \right| < k. $$

Samples

Input #1

3 3 2
3 5 1

Output #1

Input #2

5 10 3
12 8 18 25 1

Output #2

Input #3

7 7 2
7 3 4 1 6 5 2

Output #3

Input #4

2 2 2
1 3

Output #4

API Response (JSON)

{
  "problem": {
    "name": "D. Alarm Clock",
    "description": {
      "content": "Every evening Vitalya sets _n_ alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer _a__i_ — number of minute after midnight in which",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF898D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Every evening Vitalya sets _n_ alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer _a__i_ — number of minute after midnight in which...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "每天晚上，Vitalya 会设置 #cf_span[n] 个闹钟以便第二天醒来。每个闹钟恰好在一分钟内响起，其特征是一个整数 #cf_span[ai] —— 表示从午夜开始经过的第 #cf_span[ai] 分钟时响起。每个闹钟在分钟开始时响起，并在整个分钟内持续响铃。\n\n如果在某段连续的 #cf_span[m] 分钟内，至少有 #cf_span[k] 个闹钟**开始**响铃，则 Vitalya ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 2 \\cdot 10^5 $, $ 1 \\leq m \\leq 10^6 $.  \nLet $ A = \\{a_1, a_2, \\dots, a_n\\} \\subset \\{1, 2, \\dots, 10^6\\} $ be a set of ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments