Subtarea 1: Esta subtarea esta pensada para que se pueda hacer con alguna fuerza bruta, algun backtracking o un dijkstra.

Subtarea 2: Consideremos el siguiente grafo: Los nodos son los rascacielos, el nodo i, representa el rascacielos i. Por cada persona, digamos que este en la posicion id, y se pueda mover al id + d o al id - d, añadimos una arista del id al id + d con costo 1, otra del id al id + 2 d con costo 2, y asi sucesivamente, al id + x d con costo x, si id + x d < N. Ademas añadimos igualmente del id al id - d con costo 1, y asi sucesivamente. A este grafo le corremos un dijkstra del nodo que representa al rascacielos de la persona 0 y el camino de ahi al rascacielos de la persona 1 es la solucion, la complejidad es nmlogn. Esta solucion se puede mejorar a nm, al ir del id al id + x d, creamos una arista de id a un nodo auxiliar nuevo, con costo 1, y otra de este nodo auxiliar al id + d, con costo 0, para el id + 2 d, creamos otro nuevo nodo auxiliar, y añadimos una arista del nodo auxiliar anterior al nuevo nodo auxiliar con costo 1, y otra del nuevo nodo auxiliar al nodo id + 2 d, con costo 0, y asi sucesivamente, este grafo ahora tiene mas nodos, pero todas las aristas tienen costo 0 o 1, por lo cual podemos usar 0-1BFS y hacerlo todo en O(n*m).

Subtarea 3: Consideremos el siguiente grafo: Los nodos son (rascacielos,movimiento), para cada rascacielos de 1 a n y cada movimiento de 1 a n. Las aristas de primer tipo son aristas de (rascacielos,movimiento) a (rascacielos+movimiento,movimiento) con costo 1, o de (rascacielos,movimiento) a (rascacielos-movimiento,movimiento) con costo 1. Las aristas de segundo tipo son de (rascacielos,movimiento) a (rascacielos,0), con costo 0, donde (rascacielos,0) es un nodo auxiliar para facilitar las transiciones. Las aristas de tercer tipo son de (rascacielos,0) a (rascacielos,movimiento), en cada rascacielos añadimos una por cada persona que hay, si hay una persona que se mueve 3, en el rascacielos 2, añadimos una arista de (3,0) a (3,2). Un dijkstra a este grafo nos dejaria un O((n^2+m)logn) y un 0-1BFS un O(n^2+m), ambos con O(n^2) memoria.

Subtarea 4: Esta subtarea esta para alguna solucion buena, que no sea lo suficientemente rapida para pasar en la 5.

Subtarea 5: La idea general es explotar las soluciones de las subtareas 2 y 3 y combinarlas, tenemos el siguiente grafo: Los nodos son (rascacielos,movimiento), donde movimiento va de 0 a K(K es una constante que despues definiremos mejor). Para una persona, si d[i] <= K, añadimos las aristas correspondientes igual que en la subtarea 3. Si d[i] > K, añadimos las aristas correspondientes igual a la subtarea 2. (tomando (rascacielos,0) como (rascacielos) ). En total llevaremos NK nodos igual a la subtarea 2, y NN/K aristas igual a las de la subtarea 2. Una opcion intuitiva y eficiente para K es sqrt(N) o un poco menos para ahorrar memoria. Si añadimos las aristas en la parte igual a la subtarea 2 con costo sin añadir nodos auxiliares, corremos un dijkstra y queda en total en O(NsqrtNlogN), lo cual debe ser suficiente para la subtarea 4 al menos, si lo hacemos añadiendo aristas de costos 0 y 1, podemos correr un 0-1BFS y tener una solucion en O(N*sqrtN).