La última posición X31870

Disponemos de una lista ordenada de n números x₀, x₁,…, x_{n − 1} y de un número z tal que x₀ ≤ z < x_{n − 1}. Se pide una función effi_last_pos con un código muy eficiente que calcule la última posición i tal que x_i ≤ z. La función debe estar convenientemente documentada y debe utilizarse para completar el siguiente 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;
}

Puntos examen: 1.750000 Parte automática: 40.000000%

Entrada

La entrada tiene tres partes. En la primera aparece un número entero n mayor que uno. Luego hay una lista de n enteros ordenados de menor a mayor x₀, x₁,…, x_{n − 1}. Por último, encontramos una secuencia de números enteros. Cada número z de la última secuencia es tal que x₀ ≤ z y z < x_n−1.

Salida

Para cada número z de la secuencia, una línea con la última posición i donde el valor de la lista x_i no supere a z, es decir x_i ≤ z.

Observación

Las implementaciones de la función effi_last_pos que puedan tener un tiempo de ejecución proporcional a n serán invalidadas.