{"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 the largest distance between two points from this set. For example, the diameter of the multiset {1, 3, 2, 1} is 2.\n\nDiameter of multiset consisting of one point is 0.\n\nYou 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_?\n\n## Input\n\nThe first line contains two integers _n_ and _d_ (1 ≤ _n_ ≤ 100, 0 ≤ _d_ ≤ 100) — the amount of points and the maximum allowed diameter respectively.\n\nThe second line contains _n_ space separated integers (1 ≤ _x__i_ ≤ 100) — the coordinates of the points.\n\n## Output\n\nOutput a single integer — the minimum number of points you have to remove.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn the second test case the diameter is equal to 0, so its is unnecessary to remove any points.\n\nIn 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.","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第一行包含两个整数 #cf_span[n] 和 #cf_span[d]（#cf_span[1 ≤ n ≤ 100, 0 ≤ d ≤ 100]）—— 分别表示点的数量和允许的最大直径。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数（#cf_span[1 ≤ xi ≤ 100]）—— 表示各点的坐标。\n\n请输出一个整数——你需要移除的最少点数。\n\n在第一个测试用例中，最优策略是移除坐标为 #cf_span[4] 的点。剩余点的坐标为 #cf_span[1] 和 #cf_span[2]，因此直径为 #cf_span[2 - 1 = 1]。\n\n在第二个测试用例中，直径为 #cf_span[0]，因此无需移除任何点。\n\n在第三个测试用例中，最优策略是移除坐标为 #cf_span[1]、#cf_span[9] 和 #cf_span[10] 的点。剩余点的坐标为 #cf_span[3]、#cf_span[4] 和 #cf_span[6]，因此直径为 #cf_span[6 - 3 = 3]。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[d]（#cf_span[1 ≤ n ≤ 100, 0 ≤ d ≤ 100]）—— 分别表示点的数量和允许的最大直径。第二行包含 #cf_span[n] 个用空格分隔的整数（#cf_span[1 ≤ xi ≤ 100]）—— 表示各点的坐标。\n\n## Output\n\n请输出一个整数——你需要移除的最少点数。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，最优策略是移除坐标为 #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]。","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 \\leq n \\leq 100 $  \n2. $ 0 \\leq d \\leq 100 $  \n3. $ 1 \\leq x_i \\leq 100 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFind 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| $.\n\nEquivalently, find the maximum size of a subset $ S \\subseteq P $ such that $ \\max S - \\min S \\leq d $, and return $ n - |S| $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF940A","tags":["brute force","greedy","sortings"],"sample_group":[["3 1\n2 1 4","1"],["3 0\n7 7 7","0"],["6 3\n1 3 4 6 9 10","3"]],"created_at":"2026-03-03 11:00:39"}}