Fent els nombres iguals P54072


Statement
 

pdf   zip

thehtml

Tenim una col·lecció d’n nombres naturals. Repetidament, podem escollir dos nombres x i ‍y, amb x < y, esborrar y de la col·lecció, i afegir-hi x i yx. L’objectiu és aconseguir que tots els nombres siguin iguals.

Per exemple, si tenim {2, 4, 6}, podem escollir x = 4 i y = 6, passant a {2, 2, 4, 4}, escollir x = 2 i y = 4, passant a {2, 2, 2, 2, 4}, i tornar a escollir x = 2 i y = 4, passant a {2, 2, 2, 2, 2, 2}. Es pot comprovar que no és possible fer que tots els nombres siguin iguals amb menys de tres passos.

En general, quin és el mínim nombre de passos necessari?

Entrada

L’entrada conté diversos casos. Cada cas comença amb una n entre 1 i 105, seguida dels n ‍nombres, tots entre 1 i 109.

Sortida

Per a cada cas, escriviu quants passos calen per fer tots els nombres iguals.

Public test cases
  • Input

    3  2 4 6
    1  1000
    4  500000000 1000000000 500000000 500000000
    

    Output

    3
    0
    1
    
  • Information
    Author
    Félix Moreno
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python