Taules de dispersió P83317


Statement
 

pdf   zip

html

"Open Addressing" és una variant de les taules de dispersió, la qual (simplificadament) consisteix en el següent:

Sigui x una clau qualsevol, sigui MAX la mida del vector on s’emmagatzema la informació, sigui h1(x) la primera posició on s’intentarà guardar x (un valor entre 0 i MAX-1), i sigui inc un valor (el qual a vegades depèn de x) entre 1 i MAX-1. Llavors la següent posició on s’intentaria guardar x en el cas en què h1(x) ja estés ocupada seria h2(x) = (h1(x) + inc) mod MAX, la següent posició seria h3(x) = (h2(x) + inc) mod MAX, i així successivament fins a hMAX(x) = (hMAX-1(x) + inc) mod MAX. (Fixeu-vos que amb inc = 1 obtenim una de les variants de taules de dispersió que vàrem implementar en una pràctica de laboratori.)

Per exemple, si MAX = 5, h1(x) = 1 i inc = 2, les caselles del vector es visitarien (si calgués) en l’ordre següent: 1, 3, 0, 2, 4. En canvi, si MAX = 6, h1(x) = 1 i inc = 2, l’ordre seria: 1, 3, 5, 1, 3, 5. Com podeu veure, en el primer cas es visiten totes les MAX posicions, però en el segon cas no.

Escriviu un programa que decideixi, per a cada combinació de MAX, h1(x) i inc donada, si la combinació és bona (visita totes les caselles) o no ho és.

Entrada

L’entrada consisteix en zero o més casos. Cada cas consisteix en una línia amb MAX, h1(x) i inc. (Teniu la garantia de què 2 ≤ MAX ≤ 50000.) Una línia amb tres zeros marca el final de l’entrada.

Sortida

Per a cada cas, escriviu en una línia "bona" o bé "dolenta" segons convingui.

Public test cases
  • Input

    5 1 2
    6 1 2
    0 0 0
    

    Output

    bona
    dolenta
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++