Las Zamburguesas P88760


Statement
 

pdf   zip

thehtml

10

La prova de Las Zamburguesas és una de les més mítiques del concurs. Els participants han de creuar un riu saltant de roca en roca, però compte! Algunes roques són falses i s’enfonsen!

[r]

Hi ha n roques de debò, circulars, amb centre (xi, yi) i radi ri. La distància màxima que pot fer d’un salt un participant és d (mesurant-ho des de la vora de les roques). La vostra tasca és calcular el nombre mínim de salts que cal fer per anar de la primera roca a l’última sense caure a l’aigua. Si és impossible, cal indicar-ho.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de roques n ≥ 2 i la distància de salt d > 0. Segueixen n triplets de reals xi, yi i ri descrivint cada roca.

Sortida

Per a cada cas d’entrada, escriviu en una línia el nombre mínim de salts per anar de la primera de les roques donades fins a l’última, fent salts no més grans que d, o bé “Xof!” si no es pot.

Observacions

  • Els casos de prova no contindran mai roques que se solapin, ni cap salt que vagi just, i que per tant es pogués malinterpretar per errors de precisió.
  • La figura es correspon a les roques dels exemples d’entrada.
Public test cases
  • Input

    4 3
    -6 4 1  -1.5 5.5 0.5  -2.5 2 1.5  3 3 2
    4 8.3
    -6 4 1  -1.5 5.5 0.5  -2.5 2 1.5  3 3 2
    4 1
    -6 4 1  -1.5 5.5 0.5  -2.5 2 1.5  3 3 2
    

    Output

    2
    1
    Xof!
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python Python
    User solutions
    C C++ Go Java Python