Cobrint intervals P37902


Statement
 

pdf   zip

thehtml

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

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

Per exemple, si les xi’s són 1.4, 1.9, 2.3 i 2.7, una possible solució és {[1.2, 2.2], [1.8, 2.8]}, ja que cada xi es troba (com a mínim) dins d’un dels dos intervals, i no és possible cobrir els quatre reals amb un sol interval.

Entrada

L’entrada consisteix en diversos casos, cadascun dels quals amb un nombre n seguit de n ‍reals diferents. Assumiu n ≤ 105.

Sortida

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

Public test cases
  • Input

    4  1.4 1.9 2.3 2.7
    6  1.75 3.5 0.5 3 1.5 0.2
    2  -2.5 -3.5
    

    Output

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