Vector U Z30313

Un vector U és un vector d’enters que té tres parts: una baixada, una vall i una pujada. La baixada $b_1 \dots b_k$ és un subvector tal que tots els elements estan en ordre estrictament decreixent. La vall $v_1 \dots v_m$ és un subvector on tots els elements són iguals. La pujada $p_1 \dots p_n$ és un subvector tal que tots els seus valors estan en ordre estrictament creixent.

A més, es compleixen aquestes dues condicions:

1. $k \geq 1$, $m \geq 3$ i $n \geq 1$. Dit altrament: tant la baixada com la pujada tenen almenys un element, mentre que la vall en té, almenys, tres.

2. $b_k > v_1$ i $v_m < p_1$.

Per exemple, el vector V = [5 4 3 2 1 1 1 6 7 8 9 10] és un vector U:

El colze U és la posició d’un vector U on es troba $v_m$, és a dir, el darrer element de la vall. Per exemple, per al vector V = [5 4 3 2 1 1 1 6 7 8 9 10] la posició del colze U és 6, ja que és la posició on es troba el darrer element de la vall.

Has de fer la funció colzeU, que torna la posició del colze U d’un vector U.

/* PRE:  v és un vector U.
   POST: torna la posició del colze U de v.
*/

int colzeU(const vector<int>& v);

Observació

Només has d’enviar un fitxer que contingui la funció requerida, amb els include necessaris i les funcions auxiliars que hauràs declarat (si n’hi ha), i res més.

Proposeu una solució utilitzant cerca dicotòmica per aquest exercici. Qualsevol altre tipus de solució implica l’anul·lació total de tot l’exercici, independentment del veredicte del jutge.

Entrada

Un vector U d’enters.

Sortida

La posició del colze U.