Pista 1

Piensa en la factorización prima de \(N\). Como solo puedes multiplicar por \(2\) y dividir entre \(6 = 2\cdot 3\), cualquier primo distinto de \(2\) o \(3\) hace imposible llegar a \(1\).

Pista 2

Si \(N = 2^A\cdot 3^B\), necesitas exactamente \(B\) divisiones entre \(6\) para eliminar todos los \(3\). Para poder hacer esas \(B\) divisiones, debes tener al menos \(B\) factores \(2\) en total, así que si \(A < B\) primero multiplicas por \(2\) \(B-A\) veces.

Solución

Para cada caso, queremos el número mínimo de movimientos para transformar \(N\) en \(1\) usando:

\[ N \leftarrow 2N \qquad\text{y}\qquad N \leftarrow \frac{N}{6}\ \ \text{(solo si } 6\mid N\text{).} \]

1. Observación clave (factores primos)

Sea la factorización:

\[ N = 2^A \cdot 3^B \cdot R, \]

donde \(R\) no es divisible por \(2\) ni por \(3\).

• Si \(R \neq 1\), entonces \(N\) tiene algún primo distinto de \(2\) o \(3\). Ninguna operación lo elimina, así que es imposible llegar a \(1\). Se imprime \(-1\).

2. ¿Cuántas divisiones entre 6 son necesarias?

Cada vez que divides entre \(6\), reduces en \(1\) el exponente de \(2\) y en \(1\) el de \(3\):

\[ 2^A 3^B \xrightarrow{/6} 2^{A-1}3^{B-1}. \]

La única forma de disminuir el exponente de \(3\) es dividir entre \(6\). Por lo tanto, para eliminar \(3^B\) necesitas al menos \(B\) divisiones.

3. Condición de posibilidad (\(A\) vs \(B\))

Si hacemos \(B\) divisiones, consumimos \(B\) factores \(2\). Para poder completarlas, necesitamos tener al menos \(B\) "doses" disponibles en total:

\[ A + (\text{multiplicaciones por } 2) \ge B. \]

• Si \(A > B\): incluso si haces \(B\) divisiones, terminarías en \(2^{A-B}\) (ya no hay \(3\) para seguir dividiendo entre \(6\)), y multiplicar por \(2\) solo empeora. Imposible $\Rightarrow$ \(-1\).
• Si \(A \le B\): puedes multiplicar por \(2\) exactamente \(B-A\) veces para obtener \(2^B3^B\), y luego dividir \(B\) veces entre \(6\) para llegar a \(1\).

4. Mínimo de movimientos

Cuando \(R = 1\) y \(A \le B\):

• Multiplicaciones necesarias: \(B-A\).
• Divisiones necesarias: \(B\).

Total mínimo:

\[ (B-A)+B \;=\; 2B - A. \]

En resumen:

\[ \text{RESP}= \begin{cases} -1, & \text{si } R\neq 1 \text{ o } A>B,\\ 2B-A, & \text{en otro caso.} \end{cases} \]

Implementación en C++

La_Cumbia_Sonidera.cpp

Complejidad

Para obtener \(A\) y \(B\), dividimos a \(N\) repetidamente entre \(2\) y \(3\), lo cual toma \(O(log N)\) por caso. En total, \(O(T log N)\) y memoria \(O(1)\).