0xd6 - Camino más corto de la Tortuga en un arreglo circular

Tenemos un arreglo circular de N casillas numeradas de 0 a N-1. La Tortuga está inicialmente en la casilla X. Aquí hay un ejemplo con N = 7 y X = 2:

En un movimiento, la Tortuga puede moverse a cualquiera de las dos casillas vecinas a la casilla en la que está. Más especifícamente, en un movimiento la Tortuga puede:

• Moverse en la dirección de las manecillas del reloj: Si la Tortuga está en la casilla i con 0 ≤ i ≤ N-2, la Tortuga pasa a la casilla i+1. Si la Tortuga está en la casilla N-1, pasa a la casilla 0.

• Moverse en contra a la dirección de las manecillas del reloj: Si la Tortuga está en la casilla i con 1 ≤ i ≤ N-1, la Tortuga pasa a la casilla i-1. Si la Tortuga está en la casilla 0, pasa a la casilla N-1.

La Tortuga quiere llegar a la casilla Y. ¿Cuál es el mínimo número de movimientos que necesita para lograrlo?

Por ejemplo, si Y = 6, la manera más rápida de llegar es en 3 movimientos:

Entrada

La entrada contiene una única línea con 3 números enteros separados por espacios:

• N, el número de casillas en el arreglo;
• X, la casilla donde la Tortuga empieza;
• Y, la casilla a la que quiere llegar.

Está garantizado que 0 ≤ X, Y ≤ N-1 (es decir, tanto X como Y son casillas válidas dentro del arreglo).

Salida

La salida debe tener una única línea con el mínimo número de movimientos que necesita la Tortuga para llegar de la casilla X a la casilla Y.

Restricciones

• En aproximadamente 50% de los casos 1 ≤ N ≤ 50,000. En el resto de los casos 1 ≤ N ≤ 109.

Entrada de ejemplo 1

7 2 6

Salida de ejemplo 1

3

Explicación de la entrada y salida de ejemplo 1

Este es el ejemplo de la imagen. La Tortuga pasa de la casilla 2 a la 1, de la 1 a la 0 y de la 0 a la 6 para un total de 3 movimientos.

Entrada de ejemplo 2

10 9 0

Salida de ejemplo 2

1

Explicación de la entrada y salida de ejemplo 2

La Tortuga hace un movimiento en sentido horario y pasa de la casilla 9 a la 0 en un sólo movimiento.

Entrada de ejemplo 3

49937 39133 23279

Salida de ejemplo 3

15854

Envía tu solución