Recobriment amb intervals X11795

Donats un natural k i diversos nombres x₁, …, x_n, 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 {[y₁, y₁ + k], …, [y_m, y_m + k]} tal que

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

Per exemple, si k=10 i les x_i’s són 14, 19, 23 i 27, una possible solució és {[12, 22], [18, 28]}, ja que cada x_i 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 ≤ 10⁵.

Sortida

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