A. Points on the line

Codeforces

IDCF940A

Time1000ms

Memory256MB

Difficulty—

brute forcegreedysortings

English · Original

Chinese · Translation

Formal · Original

_We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round._ The **diameter** of a multiset of points on the line is the largest distance between two points from this set. For example, the diameter of the multiset {1, 3, 2, 1} is 2. Diameter of multiset consisting of one point is 0. You are given _n_ points on the line. What is the minimum number of points you have to remove, so that the diameter of the multiset of the remaining points will not exceed _d_? ## Input The first line contains two integers _n_ and _d_ (1 ≤ _n_ ≤ 100, 0 ≤ _d_ ≤ 100) — the amount of points and the maximum allowed diameter respectively. The second line contains _n_ space separated integers (1 ≤ _x__i_ ≤ 100) — the coordinates of the points. ## Output Output a single integer — the minimum number of points you have to remove. [samples] ## Note In the first test case the optimal strategy is to remove the point with coordinate 4. The remaining points will have coordinates 1 and 2, so the diameter will be equal to 2 - 1 = 1. In the second test case the diameter is equal to 0, so its is unnecessary to remove any points. In the third test case the optimal strategy is to remove points with coordinates 1, 9 and 10. The remaining points will have coordinates 3, 4 and 6, so the diameter will be equal to 6 - 3 = 3.

我们没有任何测试用例。一场大型竞赛即将来临。但出题者的首要任务应该是为本轮添加一道新题。数集在数轴上的直径是该集合中任意两点之间的最大距离。例如，数集 #cf_span[{1, 3, 2, 1}] 的直径为 2。仅包含一个点的数集的直径为 0。给你数轴上的 #cf_span[n] 个点。你需要移除最少多少个点，使得剩余点构成的数集的直径不超过 #cf_span[d]？第一行包含两个整数 #cf_span[n] 和 #cf_span[d]（#cf_span[1 ≤ n ≤ 100, 0 ≤ d ≤ 100]）—— 分别表示点的数量和允许的最大直径。第二行包含 #cf_span[n] 个用空格分隔的整数（#cf_span[1 ≤ xi ≤ 100]）—— 表示各点的坐标。请输出一个整数——你需要移除的最少点数。在第一个测试用例中，最优策略是移除坐标为 #cf_span[4] 的点。剩余点的坐标为 #cf_span[1] 和 #cf_span[2]，因此直径为 #cf_span[2 - 1 = 1]。在第二个测试用例中，直径为 #cf_span[0]，因此无需移除任何点。在第三个测试用例中，最优策略是移除坐标为 #cf_span[1]、#cf_span[9] 和 #cf_span[10] 的点。剩余点的坐标为 #cf_span[3]、#cf_span[4] 和 #cf_span[6]，因此直径为 #cf_span[6 - 3 = 3]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[d]（#cf_span[1 ≤ n ≤ 100, 0 ≤ d ≤ 100]）—— 分别表示点的数量和允许的最大直径。第二行包含 #cf_span[n] 个用空格分隔的整数（#cf_span[1 ≤ xi ≤ 100]）—— 表示各点的坐标。 ## Output 请输出一个整数——你需要移除的最少点数。 [samples] ## Note 在第一个测试用例中，最优策略是移除坐标为 #cf_span[4] 的点。剩余点的坐标为 #cf_span[1] 和 #cf_span[2]，因此直径为 #cf_span[2 - 1 = 1]。在第二个测试用例中，直径为 #cf_span[0]，因此无需移除任何点。在第三个测试用例中，最优策略是移除坐标为 #cf_span[1]、#cf_span[9] 和 #cf_span[10] 的点。剩余点的坐标为 #cf_span[3]、#cf_span[4] 和 #cf_span[6]，因此直径为 #cf_span[6 - 3 = 3]。

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ d \in \mathbb{Z}_{\geq 0} $. Let $ P = \{x_1, x_2, \dots, x_n\} \subset \mathbb{R} $ be a multiset of point coordinates. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 0 \leq d \leq 100 $ 3. $ 1 \leq x_i \leq 100 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum number of points to remove such that the diameter of the remaining multiset is $ \leq d $, where the diameter of a multiset $ S \subseteq P $ is defined as $ \max_{a,b \in S} |a - b| $. Equivalently, find the maximum size of a subset $ S \subseteq P $ such that $ \max S - \min S \leq d $, and return $ n - |S| $.

Samples

Input #1

3 1
2 1 4

Output #1

Input #2

3 0
7 7 7

Output #2

Input #3

6 3
1 3 4 6 9 10

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Points on the line",
    "description": {
      "content": "_We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round._ The **diameter** of a multiset of points on the line",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF940A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round._\n\nThe **diameter** of a multiset of points on the line...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们没有任何测试用例。一场大型竞赛即将来临。但出题者的首要任务应该是为本轮添加一道新题。\n\n数集在数轴上的直径是该集合中任意两点之间的最大距离。例如，数集 #cf_span[{1, 3, 2, 1}] 的直径为 2。\n\n仅包含一个点的数集的直径为 0。\n\n给你数轴上的 #cf_span[n] 个点。你需要移除最少多少个点，使得剩余点构成的数集的直径不超过 #cf_span[d]？\n\n第一行包含两个...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ d \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ P = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{R} $ be a multiset of point coordinates.\n\n**Constraints**  \n1. $ 1 \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments