Fent els nombres iguals P54072
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 y − x. 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.
Input
3 2 4 6 1 1000 4 500000000 1000000000 500000000 500000000
Output
3 0 1
- Author
- Félix Moreno
- Language
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python