Intervals P80417


Statement
 

pdf   zip

thehtml

Donat un conjunt de reals X={x1, x2,…, xn}, es vol trobar el conjunt més petit possible d’intervals unitaris que recobreixin tots els punts. És a dir, trobar un conjunt d’intervals I={[i1,i1+1], [i2,i2+1], …, [im,im+1]} tal que ∀ j ∣ 1≤ jn∣ ∃ k∣ 1≤ kmxj∈ [ik,ik+1] amb el mínim valor possible de m. Implementeu un algorisme voraç per resoldre aquest problema.

Entrada

L’entrada consisteix en una seqüència de reals.

Sortida

La sortida és la llista dels extrems esquerres dels intervals unitaris que recobreixen tots els punts, ordenada creixentment segons el format dels exemples.

Public test cases
  • Input

    3.2 3.6 3.7 4.5 4.6 6.8 6.9 7.3
    
    

    Output

    3.2
    4.5
    6.8
    
  • Input

    
            
                                

    Output

    
            
                                
  • Input

    1.75 3.5 0.5 3.0 1.5 0
     
    

    Output

    0
    1.5
    3
    
  • Information
    Author
    Amalia Duch
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++