0xcc - La Liebre y la Tortuga en un arreglo circular
Tenemos un arreglo circular de N casillas numeradas de 0 a N-1, donde están la Liebre y la Tortuga. La Tortuga está inicialmente en la casilla T, y la Liebre está en la casilla L. Aquí hay un ejemplo con N = 7, T = 1 y L = 6:
Cada día, la Tortuga avanza una casilla en la dirección de las manecillas del reloj (más especifícamente, 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).
La Liebre es el doble de rápida que la Tortuga: cada día la Liebre avanza el equivalente a dos movimientos de Tortuga.
En este problema nos interesa saber si la Liebre y la Tortuga se encontrarán algún día en la misma casilla. En caso afirmativo, ¿cuántos días tienen que pasar para que se encuentren?
En el ejemplo anterior, la Liebre y la Tortuga se encuentran en la casilla 3 después de 2 días:
Específicamente, esto es lo que pasa:
- Comienzo: la Tortuga está en 1 y La Liebre está en 6;
- Después de 1 día: La Tortuga está en 2 y la Liebre está 1;
- Despúes de 2 días: Ambas están en 3.
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;T, la casilla donde está la Tortuga;L, la casilla donde está la Liebre.
Está garantizado que N > 0 (el arreglo tiene por lo menos una casilla) y 0 ≤ T,L ≤ N-1 (es decir, tanto T como L son casillas válidas dentro del arreglo).
Salida
La salida debe tener una única línea con el número de días que pasan antes de que la Liebre y la Tortuga se encuentren en la misma casilla. Si nunca se encuentran, la salida debe ser una línea con la palabra Never.
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 1 6
Salida de ejemplo 1
2
Explicación del ejemplo 1
Este es el ejemplo de la imagen explicado más arriba.
Entrada de ejemplo 2
10 4 4
Salida de ejemplo 2
0
Explicación del ejemplo 2
La Tortuga y la Liebra yá están en la misma casilla (casilla 4).
Entrada de ejemplo 3
5 4 0
Salida de ejemplo 3
4
Explicación del ejemplo 3
- Después de 1 día, la Tortuga está en 0 y la Liebre está en 2;
- Después de 2 días, la Tortuga está en 1 y la Liebre está en 4;
- Después de 3 días, la Tortuga está en 2 y la Liebre está en 1;
- Después de 4 días, la Tortuga está en 3 y la Liebre está en 3.