Nombre de rotacions (1) P63069


Statement
 

pdf   zip   main.cc   main.py

thehtml

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]) -> int

Doneu 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