Nombre de rotacions (1) P63069
Donat un vector (no buit) circularment ordenat d’enters, es vol trobar el nombre de cops que s’ha rotat. Assumiu que no hi ha duplicats al vector i que la rotació és en sentit antihorari.
Per exemple,
[8, 9, 10, 2, 5, 6] s’ha rotat tres cops,
[9, 10, 2, 5, 6, 8] s’ha rotat dos cops,
[4, 0, 1, 2, 3] s’ha rotat un cop, i
[2, 5, 8, 9, 12] s’ha rotat zero cops.
Resoleu aquest problema iterativament en temps logarítmic, usant aquesta capçalera per C++:
int number_of_rotations (const vector<int>& v);O aquesta per Python:
number_of_rotations(v: list[int]) -> intDoneu l’invariant del bucle en un comentari a l’inici del bucle de la funció.
Observació
Només cal enviar el procediment demanat; el programa principal serà ignorat.
Information
- Author
- Jordi Petit
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python