Número más pequeño
A Bitman le gusta jugar con listas de números distintos de cero. El tiene muchas de tales listas. Para matar el aburrimiento, el toma alguna lista y busca el número más pequeño en esta. Sin embargo, pronto perdió el interés en hacerlo porque era demasiado fácil, por lo que decidió crear una nueva lista utilizando este procedimiento:
- las listas son 1-indexadas -
procedimiento GenerarLista (A, B, x):
sea n = longitud de A
sea m = longitud de B
sea L = una lista vacía
para i de 1 a min (n, m - x), inclusive:
para j desde (i + x) hasta m, inclusive:
Agregue (A[i] * B[j]) al final de L
devolver L
Para crear L, el toma dos listas A y B y un entero x y llama al subprograma . El estaba sorprendido al ver una lista tan grande y decidió encontrar el número más pequeño en esta. Puede usted ayudarlo ?
Observe que número más pequeño en una lista L es el elemento de L cuando esta es ordenada. Por ejemplo, el número más pequeño en es 7.
Entrada
La primera línea contiene cuatro enteros n, m, x y k separados entre si por espacios. Los tamaños respectivos de y son n y m. La segunda línea contiene n enteros separados entre si por espacio en blanco. La tercera línea contiene m enteros separados entre si por espacio en blanco.
Restricciones
Salida
Imprimir una sola línea que contenga un entero denotando la respuesta: el número más pequeño en la lista L.
Ejemplo de Entrada
3 4 1 5
2 -3 1
3 1 -2 -1
Ejemplo de Salida
3
Explicación
La lista L se obtiene después de llamar a . Encontramos que . Por lo tanto, el número más pequeño en L es 3.
Comments
Búsqueda binaria: digamos que es la cantidad de números en la lista menores o iguales a ; es obvio que es no decreciente, así que puedes aplicar búsqueda binaria para encontrar el menor tal que . Ahora solo necesitas computar , iteramos por las y para cada una tenemos que contar cuántas .
Si : contamos todos los si , ya que ; si no contamos niguno.
Si : tenemos que contar cuántas .
Si : tenemos que contar cuántas .
Entonces podemos mantener un ABI, y si iteramos por decrecientemente para un tenemos en el ABI a , entonces para solo tenemos que agregar . Hacemos operaciones en cada momento de la búsqueda binaria, por lo que corre en tiempo .
Man disculpa la molestia pero como tu haces para crear ese ABI con los valores negativos yo la función del ABI la quise hacer con un persistent pero se me marea con los valores negativos.
Yo lo programé usando dos ABI, uno para los negativos y uno para los positivos, pero puedes tener un solo sumándole a cada valor, así cuando vayas a sumarle 1 a la posición lo que haces sumar 1 en la posición .
Gracias men
Si necesitas más detalles solo dilo.
Alguna idea d como hacer este problema?
te lo puse arriba