L'última posició X31870

Disposem d’una llista ordenada de $n$ nombres $x_0, x_1,\ldots, x_{n - 1}$ i d’un nombre $z$ tal que $x_0 \le z < x_{n - 1}$. Es demana una funció effi_last_pos amb un codi molt eficient que calculi l’última posició $i$ tal que $x_i \le z$. La funció ha d’estar convenientment documentada i s’ha d’utilitzar per completar el següent programa.

#include <iostream>
#include <vector>
using namespace std;


///////////////////////////////////////////
//
// documentation and code of effi_last_pos 
// function must be here
//
///////////////////////////////////////////


//gets vector v from input chanel
void read_vector(vector<int>& v) {
    int n = v.size();
    for (int i = 0; i < n; ++i) cin >> v[i];
}


int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    read_vector(v);
    int z;
    while (cin >> z)
        cout << effi_last_pos(v, z) << endl;
}

Punts examen: 1.750000 Part automàtica: 40.000000%

Entrada

L’entrada té tres parts. En la primera apareix un nombre enter $n$ més gran que un. Després hi ha una llista de $n$ enters ordenats de menor a major $x_0, x_1, \ldots, x_{n - 1}$. Finalment, trobem una seqüència de nombres enters. Cada número $z$ de l’última seqüència és tal que $x_0 \le z$ i $z < x_{n-1}$.

Sortida

Per a cada nombre $z$ de la seqüència, una línia amb l’última posició $i$ on el valor de la llista $x_i$ no superi a $z$, és a dir $x_i \le z$.

Observació

Les implementacions de la funció effi_last_pos que puguin tenir un temps d’execució proporcional a $n$ seran invalidades.