codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

940A.md (1797B)


      1 Source: https://codeforces.com/problemset/problem/940/A
      2 
      3 A. Points on the line
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 Diameter of multiset consisting of one point is 0.
     26 
     27 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*?
     28 
     29 Input
     30 
     31 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.
     32 
     33 The second line contains *n* space separated integers (1 ≤ *x**i* ≤ 100) — the coordinates of the points.
     34 
     35 Output
     36 
     37 Output a single integer — the minimum number of points you have to remove.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 1  
     45 2 1 4
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 1
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 3 0  
     58 7 7 7
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 6 3  
     71 1 3 4 6 9 10
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 3
     78 ```
     79 
     80 Note
     81 
     82 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.
     83 
     84 In the second test case the diameter is equal to 0, so its is unnecessary to remove any points.
     85 
     86 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.