Nombres consecutius a distancia menor o igual a 2, només dos consecutius a distància 1. X96493
En aquest exercici heu d’implementar una funció que rep un vector d’enters que cumpleix el següent. Qualsevol parella de valors consecutius d’aquest vector es troben a una distància menor o igual a 2. Però, a més, només hi ha exactament una parella de valors consecutius d’aquest vector que es troben a distància exactament 1. Per exemple, la següent seqüencia de valors cumpleix aquesta condició:
3 1 1 2 4 2 2 0
La funció ha de retornar la posició (indexant des de 0) del primer element de la parella consecutiva que es troben a distància 1. Amb l’exemple anterior com a entrada, la funció ha de retornar 2.
Aquesta és la capçalera:
// Pre: Sigui n el tamany v.size(). Llavors, per a cada i a {0..n-2}, es compleix |v[i]-v[i+1]|<=2.
// A més, només hi ha un i a {0..n-2} que compleixi |v[i]-v[i+1]|=1.
// Post: La funció retorna el i praticular que compleix |v[i]-v[i+1]|=1.
int positionDistance1(const vector<int> &v);
Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.
Observació
Avaluació sobre 10 punts:
- Solució lenta: 5 punts.
- solució ràpida: 10 punts.
Entenem com a solució ràpida una que és correcta, de cost logarítmic i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.
positionDistance1([-1, -1, 0, 0]) = 1 positionDistance1([5, 5, 7, 7, 9, 9, 11, 10, 8, 6, 6, 6]) = 6 positionDistance1([2, 0, 2, 4, 6, 6, 6, 6, 8, 7, 5, 3]) = 8 positionDistance1([-9, -9, -9, -10, -12, -14]) = 2 positionDistance1([10, 10, 12, 14, 15]) = 3 positionDistance1([9, 9, 11, 13, 11, 13, 15, 15, 15, 16, 14, 16, 14, 16, 18, 18]) = 8 positionDistance1([4, 2, 0, -2, -4, -5, -7, -5, -3, -5]) = 4 positionDistance1([-7, -9, -7, -5, -6]) = 3 positionDistance1([-2, -2, -4, -6, -4, -6, -6, -6, -6, -8, -10, -8, -7, -7, -5, -5]) = 11 positionDistance1([4, 6, 7, 5, 5, 7, 7, 9, 11]) = 1 positionDistance1([10, 10, 12, 12, 10, 8, 8, 9, 11, 9, 11, 9]) = 6 positionDistance1([0, 2, 0, -2, -1, -1, 1, 3, 5, 5, 3, 5, 7]) = 3 positionDistance1([-7, -9, -9, -7, -7, -6, -8, -6, -4, -4, -2, -4, -4, -2]) = 4 positionDistance1([-8, -6, -6, -4, -4, -4, -2, -2, -4, -4, -2, 0, -2, -4, -2, -2, -4, -5, -5]) = 16 positionDistance1([3, 5, 7, 6]) = 2 positionDistance1([6, 7, 7]) = 0 positionDistance1([7, 9, 10]) = 1 positionDistance1([5, 7, 7, 8, 8, 10, 12, 14, 14, 14, 14, 12, 10, 8, 6, 8, 6, 8]) = 2 positionDistance1([-2, 0, 2, 2, 4, 4, 2, 3, 5, 7, 7, 5, 7, 5]) = 6 positionDistance1([5, 3, 2, 4, 6]) = 1