Vamos a definir nuestros dos posibles movimientos de la siguiente manera:
- Una pasta (P) , se añade el número de caracteres en el portapapeles para el mensaje,
tomar de 1 paso.
- Una copia (C) establece el número de caracteres en el portapapeles para igualar el número de
de caracteres en el mensaje, tomar 3 pasos (seleccionar todo, copiar, seleccione la final). (Lado
nota: usted puede hacer la misma cosa con seleccionar todo, copiar, pegar - te va a pegar más
su texto seleccionado, reemplazándolo con sí mismo. Nota 2: yo estoy usando una diferente
definición de "copia" de otros: no estoy incluyendo la pasta de la copia.)
La pregunta es, si usted comienza con 1 personaje en el mensaje y 1 carácter en el
portapapeles, ¿cuántos pasos (mínimo) tardará en llegar, al menos, 1000 caracteres en
el mensaje?
La secuencia de movimientos (Ps y Cs) se utiliza de forma óptima va a ver algo como
este:
PPPCPPCPCPPPCP
(Es inútil empezar o terminar con una C, y poner dos Cs uno al lado del otro es
igualmente inútiles). Así, de manera óptima, haremos $a_1$ Ps, seguido por una C, seguido por
$a_2$ Ps, seguido por una C, etc., terminando con una C y $a_m$ Ps, donde cada una de las $a_i \ge 1$. El número de pasos que se utiliza en esta forma se
$$
a_1 + a_2 + \cdots + a_m + 3(m-1). \etiqueta{1}
$$
Now, let $K_n$ be the position with $n$ characters in the message and $$ n caracteres
en el portapapeles. De $K_n$, si utilizamos $a$ Ps en una fila, seguido por una C, terminamos
en la posición $K_{n(a+1)}$. Podemos asumir que obtener una copia gratuita de mover al final (es
no va a mejorar el número de caracteres en el mensaje), por lo que nuestra posición final
es $K_A$ donde $A$ está dado por
$$
(a_1 + 1)(a_2 + 1)\cdots(a_m + 1) \etiqueta{2}
$$
Lo que queremos es maximizar (2), mientras que al mismo tiempo reducir al mínimo (1). Más concretamente, si
podemos cambiar el $a_i$s a disminuir (1) y aumento (2), esto es, sin duda
bueno. A partir de esta idea, podemos observar:
- Incluso una $a \ge 8$ debe ser reemplazado por $1$$\frac{a}{2}$. En (2), podemos mejorar
desde $(a + 1) \le (1 + 1)(\frac{a}{2} + 1)$. En (1) podemos mejorar ya que $a \ge 1 +
\frac{a}{2} + 3$. (The $+ 3$ comes from $m$ increasing by $1$.)
- Una extraña $a \ge 7$ debe ser reemplazado por $1$$\frac{a-1}{2}$. Tenemos $(a + 1)
\le (1 + 1)(\frac{a-1}{2} + 1)$ and $un \ge 1 + \frac{a-1}{2} + 3$.
- Si $a$$a'$, $a < a'$ son al menos dos separados, se deberá reemplazarlos con $a + 1$$a' - 1$. Tenemos $(a + 1)(a' + 1) \le (a + 2)(a')$$a + a' \ge (a + 1) + (a' - 1)$.
Los tres simplificaciones, cuando se aplica tantas veces como necesitemos, nos dan un conjunto final de $a_1,a_2,\dots,a_m$ que pertenecen a $\{1,2,3,4,5,6\}$ y no contienen dos $a_i$s de dos o más de distancia. En otras palabras, es óptimo para el uso de cualquiera de las $1$s y $2$s, $2$s y $3s$, $3$s y $4$s, $4$s y $5$s o $5$s y $6$s solo. Pero podemos ir más allá. Se puede comprobar que, en la (multi)set $a_1,a_2,\dots,a_m$:
- $1,1$ puede ser sustituido por $3$
- $1,2$ puede ser sustituido por $5$
- $5,5$ puede ser sustituido por $2,2,3$
- $6,6$ puede ser sustituido por $3,3,3$
Por lo tanto, de manera óptima, tenemos que usar al menos una $5$, en más de una $6$ y en más de una $1$.
También, ya que no podemos utilizar tanto en $1$s y $2$s, $1$s son bastante inútil (el único momento en el $a_i = 1$ se bien es si sólo hay un $a_i$ total).
Esto arroja fuera el caso de que sólo utilizamos $1$s y $2$s.
Finalmente, sólo el uso de $5$s y $6$s podemos conseguir en la mayoría de $(5 + 1)(6 + 1) = 42$, que es mucho menos de $1000$, así que vamos a tirar este caso. Nos quedamos con sólo tres casos: utilizamos $2$s y $3$s, utilizamos $3$s y $4$s, o utilizamos $4$s y en más de una $5$.
En este punto, vamos a suponer que sólo utilizamos $b$s y $b+1$s, donde $b \in \{2,3,4\}$.
Deje $a_i = b$ $j$ valores de $i$, y deje $a_i = b + 1$ $k$ valores de $i$.
Entonces a partir de (1), es necesario minimizar
$$
(b)j + (b + 1)k + 3 j + k - 1) = (b + 3)j + (b + 4)k - 3 \etiqueta{3}
$$
Dado que (2) es, al menos,$1000$, es decir,
$$
(b + 1)^j (b + 2)^k \ge 1000. \etiqueta{4}
$$
We separate into cases on $b$ to complete the work.
Case 1: $b = 2$
Here (4) becomes $3^j 4^k \ge 1000$.
Dado un fijo $k$, queremos elegir el más pequeño $j$ para que esto se cumple.
También, recogiendo $k > 5$ es inútil desde $4^5 > 1000$ ya.
\begin{array}{|c|c|c|}
\hline
k & \text{Smallest } j & 3^j 4^k & \text{Steps used (3): } 5j + 6k - 3
\\ \hline
0 & 7 & 2187 & 32
\\ \hline
1 & 6 & 2916 & 33
\\ \hline
2 & 4 & 1296 & 29
\\ \hline
3 & 3 & 1728 & 30
\\ \hline
4 & 2 & 2304 & 31
\\ \hline
5 & 0 & 1024 & 27
\\ \hline
\end{array}
Caso 2: $b = 3$
(4) se convierte en $4^j 5^k \ge 1000$.
Dado un fijo $k$, queremos elegir el más pequeño $j$ para que esto se cumple.
Recogiendo $k > 5$ es inútil desde $5^5 > 1000$ ya.
Asumimos $k > 0$ desde $k = 0$ se engloba en el Caso 1.
\begin{array}{|c|c|c|}
\hline
k & \text{Smallest } j & 4^j 5^k & \text{Steps used (3): } 6j + 7k - 3
\\ \hline
1 & 4 & 1280 & 28
\\ \hline
2 & 3 & 1600 & 29
\\ \hline
3 & 2 & 2000 & 30
\\ \hline
4 & 1 & 2500 & 31
\\ \hline
5 & 0 & 3125 & 32
\\ \hline
\end{array}
Caso 3: $b = 4$
(4) se convierte en $5^j 6^k \ge 1000$.
Hemos observado antes de que $k \ge 2$ es subóptima.
También, $k = 0$ es englobado en el Caso 2.
Por lo tanto nuestra tabla es muy simple:
\begin{array}{|c|c|c|}
\hline
k & \text{Smallest } j & 5^j 6^k & \text{Steps used (3): } 7j + 8k - 3
\\ \hline
1 & 4 & 3750 & 33
\\ \hline
\end{array}
$$
* \quad * \quad *
$$
Después de haber pasado por todos los casos, podemos ver que, efectivamente, el 27 de pasos es lo mejor que podemos hacer. Nuestra estrategia es PPPCPPPCPPPCPPPCPPP, y terminamos con 1024 caracteres.
Comentarios Finales:
El final de la computación era un poco bruto, pero considerablemente más fácil de lo esperado (y factible a mano!).
Este método de reducción de los casos $b = 2$, $b = 3$, y $b = 4$, y luego el control de cada uno debe ser fácil para el programa en un equipo para un general $N$ número deseado de caracteres ($N = 1000$ aquí).
Habrá cerca de $\log_4 N$ filas de la primera tabla, $\log_5 N$ filas de la segunda tabla, y $1$ fila en la tercera tabla; por lo tanto el algoritmo tendrá
tiempo total $\log_4 N + \log_5 N + 1$, o, simplemente,$O(\log N)$, que es casi tan eficiente como podemos pedir.
