Recobriment amb intervals P76554


Statement
 

pdf   zip

thehtml

Donats un natural k i diversos nombres x1, …, xn, es vol trobar el conjunt més petit possible d’intervals tancats de mida k que cobreixin aquests nombres. En altres paraules, cal trobar un conjunt d’intervals {[y1, y1 + k], …, [ym, ym + k]} tal que

  • per a cada xi, existeixi alguna j tal que xi ∈ [yj, yj + k];
  • la m sigui mínima.

Per exemple, si k=10 i les xi’s són 14, 19, 23 i 27, una possible solució és {[12, 22], [18, 28]}, ja que cada xi es troba (com a mínim) dins d’un dels dos intervals, i no és possible cobrir els quatre nombres amb un sol interval.

Entrada

L’entrada consisteix en diversos casos, cadascun dels quals comença amb k, seguit n, seguits de n nombres diferents. Tots els nombres de l’entrada són enters. Assumiu 1 ≤ k, n ≤ 105.

Sortida

Per a cada cas, escriviu el nombre mínim d’intervals tancats de mida k que cobreixin els nombres donats.

Public test cases
  • Input

    10  4  14 19 23 27
    100 6  175 350 50 300 150 20
    10  2  -25 -35
    

    Output

    2
    3
    1
    
  • Information
    Author
    Enric Rodriguez
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++