Nombres consecutius a distancia menor o igual a 1, només dos consecutius a distància 0. X18012


Statement
 

pdf   zip   main.cc

thehtml

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 1. Però, a més, només hi ha exactament una parella de valors consecutius d’aquest vector que es troben a distància exactament 0, és a dir, que son iguals. Per exemple, la següent seqüencia de valors cumpleix aquesta condició:

3 2 1 2 3 4 3 3 2 1 2 3 4 5 6 5

La funció ha de retornar la posició (indexant des de 0) del primer element de la parella consecutiva que es troben a distància 0, és a dir, que son iguals. Amb l’exemple anterior com a entrada, la funció ha de retornar 6.

Aquesta és la capçalera: 

// Pre: Sigui n la mida v.size(). Llavors, n>=2.
//      A més, per a cada i a {0..n-2}, es cumpleix |v[i]-v[i+1]|<=1.
//      A més, hi ha exactament un i a {0..n-2} que cumpleix |v[i]-v[i+1]|=0.
// Post: La funció retorna el i particular a {0..n-2} que cumpleix |v[i]-v[i+1]|=0.
int positionDistance0(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.

Sample session 
positionDistance0([-1, 0, 0, 1]) = 1
positionDistance0([-1, 0, 0, 1, 0, 1, 0, 1, 2, 1]) = 1
positionDistance0([6, 5, 6, 6, 5, 6, 7, 6, 5]) = 2
positionDistance0([-9, -8, -7, -8, -9, -10, -9, -9]) = 6
positionDistance0([-3, -2, -2, -3, -2, -1, 0]) = 1
positionDistance0([0, 0, -1]) = 0
positionDistance0([5, 6, 5, 6, 5, 4, 4, 5, 4, 3, 2]) = 5
positionDistance0([-4, -5, -4, -5, -4, -5, -4, -3, -2, -3, -2, -2, -3, -2, -3, -2, -3, -4]) = 10
positionDistance0([-3, -3]) = 0
positionDistance0([4, 3, 2, 3, 4, 3, 4, 3, 2, 1, 0, 1, 0, 0, -1]) = 12
positionDistance0([4, 4, 5, 4, 3, 2, 3]) = 0
positionDistance0([10, 11, 10, 9, 8, 9, 8, 7, 7, 8, 9, 10, 9, 10, 9]) = 7
positionDistance0([-6, -5, -4, -3, -3, -2, -1, 0, 1, 0, 1, 2, 1]) = 3
positionDistance0([-2, -1, -1, -2, -3, -2]) = 1
positionDistance0([-7, -6, -7, -8, -9, -8, -9, -8, -9, -8, -9, -8, -9, -8, -8, -7, -6]) = 13
positionDistance0([-8, -9, -8, -9, -8, -9, -10, -11, -12, -13, -12, -13, -12, -11, -10, -9, -8, -8, -9]) = 16
positionDistance0([4, 3, 3, 4, 5, 4, 5, 4, 5, 6, 7]) = 1
positionDistance0([7, 6, 6]) = 1
positionDistance0([8, 9, 8, 7, 8, 9, 10, 10, 9, 8]) = 6
positionDistance0([6, 5, 4, 5, 6, 6, 7]) = 4
Information
Author
PRO1
Language
Catalan
Official solutions
C++
User solutions
C++