Copiado al portapapeles
Descripción
Luffy al fin tendrá su pelea contra Kaido asi que para empezar el usará un nuevo ataque llamado red roc.
Como Luffy es un hombre de goma tiene la capacidad de estirarse, pero para su nuevo ataque va a estirar solo su puño.
Supongamos que su puño está en la posición $v$. En una operación Luffy puede usar una de las 2 opciones siguientes:
- Estirar su puño de la posición $v$ a $(v+1) \% 32768$
- Estirar su puño de la posición $v$ a $(v*2) \% 32768$
Como Kaido esta tan confiado de que ganará la pelea y no Luffy, permanecerá en la posición $0$.
Luffy intentó estar preparado en todo lo posible para su pelea entonces el pensó en $n$ números: $a_{1}$, $a_{2}$,..., $a_{n}$, los cuales son las posibles posiciones iniciales en donde el podría empezar su nuevo ataque y por ende su puño empieza en esa posición también.
¿Cuál es el número mínimo de operaciones que necesita para hacer que cada $a_{i}$ sea igual a $0$ y le llegué el nuevo ataque a Kaido?
Entrada
La primera línea contiene un entero único $n$ $(1 \leq n \leq 32768)$ – la cantidad de números en los que Luffy pensó para atacar.
La segunda línea contiene $n$ enteros: $a_{1}$, $a_{2}$, .., $a_{n}$ $(0 \leq ai <32768)$, son las posibles posiciones de donde Luffy podría empezar su nuevo ataque(Si el empieza en $a_{i}$ por ende su puño también).
Salida
Imprimir $n$ enteros. El número entero $i$-ésimo debe ser igual al número mínimo de operaciones requeridas para que Luffy empiece su ataque en la posición $a_{i}$ y su puño se estire hasta llegar a la posición $0$ en donde se encuentra Kaido. Mostrar los elementos con un espacio entre cada 2 elementos
Ejemplo Entrada
4 19 32764 10240 49
Ejemplo Salida
14 4 4 15
Ayuda
Del ejemplo de entrada consideremos cada $a_{i}$:
$a_{1} = 19$. Si el ataque empieza en esta posición, podría estirarse usando la opción 1 para llegar a $20$ y luego usar la opción 2 unas 13 veces. Entonces llegará a la posición 0 en 1+13 = 14 operaciones.
$a_{2} = 32764$. Puede usar la opción 1 unas 4 veces: $32764 → 32765 → 32766 → 32767 → 0$.
$a_{3} = 10240$. Puede usar la opción 2 unas 4 veces: $10240 → 20480 → 8192 → 16384 → 0$.
$a_{4} = 49$. Puede usar la opción 2 y serán 15 operaciones.
Breadth-first search