ACM 2016 - Round #1Ended |
Este año, el Real Madrid intentará ganar el trofeo de la UEFA Champions League contra el FC Barcelona. Es tradición que los dos equipos entonen sus himnos nacionales primero. Para lograr esto todos los jugadores(hay en total N personas en cada equipo) forman dos líneas. Cada equipo se encuentra en una mitad del campo y las dos mitades estan divididas por la línea $y=0$. Los del Real Madrid se pararán sobre la línea $y=1$ y los miembros de Barcelona en la línea $y=-1$. Es decir el iésmo miembro del Madrid tendrá coordenadas $(r_i, 1)$ y los del Barcelona $(b_i , -1)$.
Luego de los himnos cada uno debe pararse en la línea del medio$(y=0)$ para la foto. El fotógrafo principal les pide que deben formar una sola línea tal que la distancia entre dos jugadores consecutivos sea de exactamente uno. Tu tarea es averiguar donde se debe parar cada persona. Para hacer la tarea mas interesante debes minimizar la suma de las distancias recorridas por cada persona.
La primera línea de la entrada contiene un entero $N (1 \leq N \leq 10^5)$. La segunda línea contiene N enteros $r_i$ $(-10^6 \leq r_i \leq 10^6)$. La tercera línea contiene $N$ enteros $c_i$ $(-10^6 \leq c_i \leq 10^6)$. Pueden haber dos jugadores sobre la misma coordenada(Estos se consideran puntos desde la vista del helicóptero).
Imprima un número real: la mínima suma de las distancias viajadas por cada persona redondeada a 2 lugares luego de la coma.
En el ejemplo el lugar óptimo de ubicar a las personas en una línea es en las coordenadas: $ (0.3964673051113727, 0), (1.3964673051113727, 0), ..., (5.3964673051113727, 0)$.