Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 4
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves
La observación principal de este problema es que siempre hay
lugares estables para el meteorito, y que cada uno de éstos se encuentra entre parejas consecutivas de planetas. Primero notemos que ningún lugar estable puede estar más a izquierda que todos los planetas, ya que la fuerza neta sobre éste lo haría moverse a la derecha. Por la misma razón, no pueden haber lugares estables después del último planeta hacia la derecha.
Ahora, para ver que siempre hay un lugar estable entre cualquier pareja consecutiva de planetas hay que analizar la función que describe la fuerza entre el meteorito y el planeta:
. Supongamos que el meteorito está entre los planetas
e
. Cuando
la fuerza que atrae al meteorito hacia el planeta
es suficientemente grande para forzar al meteorito a moverse a la izquierda sin importar la fuerza de los planetas que se encuentren a la derecha (nota que el denominador se hace muy pequeño). Lo mismo ocurre con el planeta
cuando el meteorito está muy cerca de él. Pero esto quiere decir que existe un único punto
entre los dos planetas en el que la fuerza neta sobre el meteorito es 0. (Este argumento se puede formalizar utilizando cálculo.)
Además, es sencillo observar que el meteorito se movería a la izquierda si estuviera entre el planeta
y el punto
, y a la derecha si estuviera entre el punto
y el planeta
. Por lo tanto, podemos hacer una búsqueda binaria para encontrar el punto
para cada pareja de planetas consecutivos.
Como hay
parejas y calcular la fuerza neta sobre el meteorito en algún punto arbitrario toma tiempo
, la complejidad total de este algoritmo es
donde
es la cantidad de iteraciones que realice la búsqueda binaria. También hay que ordenar los planetas, ya que la descripción del problema no asegura que vendrán ordenados. Por lo tanto, la solución final tiene complejidad
.
El siguiente código implementa esta solución: