|
|
|
SALTS
Imaginem un camí rodó dividit en n caselles numerades de l'1 al n començant per una casella determinada i seguint el sentit de les agulles del rellotge.
Si comencem des de la casella m1 i fem salts de la mateixa magnitud k > 0 en el sentit de les agulles del rellotge, tindrem una seqüència periòdica de caselles de període més petit o igual que n. Per exemple, si n = 8, m1 = 3 i k = 5, la seqüència, que tindrà període 8, serà:
3, 8, 5, 2, 7, 4, 1, 6, 3, 8, 5, 2, 7, 4, 1, 6, 3, 8, 5, 2, 7, 4, 1, 6, ...
És fàcil comprovar que, si n i k són primers entre ells, la seqüència tindrà període n, en cas contrari, si n i k tenen divisors comuns diferents d'1, la seqüència tindrà període més petit que n (concretament un divisor de n). Per exemple, si n = 8 , m1 = 3 i k = 6, la seqüència, que tindrà període 4, serà:
3, 1, 7, 5, 3, 1, 7, 5, 3, 1, 7, 5 , ...
Es demana: Fer un programa que
llegeixi les dades n, m1, m2 i k i calculi
el nombre mínim de salts necessaris per arribar des de la casella m1
a la casella m2, fent salts de mida k en el sentit
de les agulles del rellotge, en un camí rodó dividit en n caselles.
El programa ha de preveure el cas en que no es pugui assolir
la casella m2. També ha de considerar el cas m1=
m2, cas en el qual es considerarà que el nombre mínim de salts
serà 0.
Les dades d'entrada es llegiran d'un fitxer de text anomenat: SALTS.IN
Els nombres m1, i m2
seran més petits o iguals a n. No fa falta
la comprovació d'aquesta circumstància.
Les dades de sortida s'escriuran en el fitxer de
text: SALTS.OUT En aquest fitxer, el programa escriurà un nombre enter més
petit o igual a n, en el cas de que es pugui assolir la casella m2,
o bé la paraula impossible en el cas de que no es pugui. EXEMPLES:
|
SALTS.IN |
SALTS.OUT |
|
8 3 7 5 |
4 |
|
8 3 3 5 |
0 |
|
8 3 8 6 |
impossible |
Tornar