Número máximo de caracteres mediante las pulsaciones de teclas A, Ctrl + A, Ctrl + C y Ctrl + V

Esta es una pregunta de entrevista de Google. No puedo resolverlo solo. ¿Alguien puede arrojar algo de luz?

Escriba un programa para imprimir la secuencia de pulsaciones de teclas de modo que genere el número máximo de caracteres 'A'. Usted está autorizado a utilizar sólo 4 teclas: A, Ctrl+ A, Ctrl+ Cy Ctrl+ V. Solo se permiten N pulsaciones de tecla. Todos los Ctrlcaracteres + se consideran como una pulsación de tecla, por lo que Ctrl+ Aes una pulsación de tecla.

Por ejemplo, la secuencia A, Ctrl+ A, Ctrl+ C, Ctrl+ Vgenera dos A de en 4 pulsaciones de teclas.

• Ctrl + A es Seleccionar todo
• Ctrl + C es Copiar
• Ctrl + V es Pegar

Hice algunas matemáticas. Para cualquier N, usando x números de A, uno Ctrl+ A, uno Ctrl+ Ce y Ctrl+ V, podemos generar un máximo de ((N-1) / 2) ² números de A. Para algunos N> M, es mejor utilizar la mayor cantidad Ctrl+ A's, Ctrl+ Cy Ctrl+ Vsecuencias, ya que duplica el número de Atléticos.

La secuencia Ctrl+ A, Ctrl+ V, Ctrl+ Cno sobrescribirá la selección existente. Anexará la selección copiada a la seleccionada.

Hay una solución de programación dinámica. Empezamos sabiendo que las teclas 0 pueden convertirnos en 0 A. Luego iteramos ihasta n, haciendo dos cosas: presionando A una vez y presionando seleccionar todo + copiar seguido de pegar jveces (en realidad j-i-1debajo; observe el truco aquí: el contenido todavía está en el portapapeles, por lo que podemos pegarlo varias veces sin copiando cada vez). Solo tenemos que considerar hasta 4 pegadas consecutivas, ya que seleccionar, copiar, pegar x 5 equivale a seleccionar, copiar, pegar, seleccionar, copiar, pegar y esto último es mejor ya que nos deja con más en el portapapeles. Una vez que llegamos n, tenemos el resultado deseado.

La complejidad puede parecer O (N), pero dado que los números crecen a una tasa exponencial, en realidad es O (N ² ) debido a la complejidad de multiplicar los números grandes. A continuación se muestra una implementación de Python. Se necesitan unos 0,5 segundos para calcular N = 50.000.

def max_chars(n):
  dp = [0] * (n+1)
  for i in xrange(n):
    dp[i+1] = max(dp[i+1], dp[i]+1) # press a
    for j in xrange(i+3, min(i+7, n+1)):
      dp[j] = max(dp[j], dp[i]*(j-i-1)) # press select all, copy, paste x (j-i-1)
  return dp[n]

En el código, jrepresenta el número total de teclas presionadas después de nuestra nueva secuencia de pulsaciones de teclas. Ya tenemos ipulsaciones de teclas en esta etapa, y 2 pulsaciones nuevas van a seleccionar todo y copiar. Por lo tanto, estamos alcanzando j-i-2tiempos de pegado . Dado que pegar se suma a la secuencia existente de dp[i] A's, debemos agregar 1make it j-i-1. Esto explica el j-i-1en la segunda y última línea.

Aquí hay algunos resultados ( n=> número de A):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• 1,000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• 50.000 => ¡ un número muy grande!

Estoy de acuerdo con @SB en que siempre debes establecer tus suposiciones: la mía es que no necesitas pegar dos veces para duplicar la cantidad de caracteres. Esto obtiene la respuesta para 7, así que a menos que mi solución sea incorrecta, la suposición debe ser correcta.

En caso maravillas alguien por qué no estoy de cheques secuencias de la forma Ctrl+ A, Ctrl+ C, A, Ctrl+ V: El resultado final siempre será el mismo que A, Ctrl+ A, Ctrl+ C, Ctrl+ V, que yo no considero.

Al usar la solución de marcog, encontré un patrón que comienza en n=16. Para ilustrar esto, aquí están las pulsaciones de teclas para n=24hasta n=29, reemplacé ^ A con S (seleccionar), ^ C con C (copiar) y ^ V con P (pegar) para facilitar la lectura:

24: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P
       4   *    4    *    4    *    4    *    4     = 1024
25: A,A,A,A,S,C,P,P,P,S,C,P,P,S,C,P,P,S,C,P,P,S,C,P,P
       4   *    4    *   3   *   3   *   3   *   3    = 1296
26: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,S,C,P,P,S,C,P,P
       4   *    4    *    4    *   3   *   3   *   3    = 1728
27: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,S,C,P,P
       4   *    4    *    4    *    4    *   3   *   3    = 2304
28: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P
       4   *    4    *    4    *    4    *    4    *   3    = 3072
29: A,A,A,A,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P,S,C,P,P,P
       4   *    4    *    4    *    4    *    4    *    4     = 4096

Después de 4 As iniciales, el patrón ideal es seleccionar, copiar, pegar, pegar, pegar y repetir. Esto multiplicará el número de As por 4 cada 5 pulsaciones de tecla. Si este patrón de 5 pulsaciones no puede consumir las pulsaciones restantes por sí solo, algunos patrones de 4 pulsaciones (SCPP) consumen las pulsaciones finales, reemplazando a SCPPP (o eliminando una de las pastas) según sea necesario. Los 4 patrones de pulsación de teclas multiplican el total por 3 cada 4 pulsaciones.

El uso de este patrón aquí es un código de Python que obtiene los mismos resultados que la solución de marcog, pero es O (1) editar : esto es en realidad O (log n) debido a la exponenciación, gracias a IVlad por señalar eso.

def max_chars(n):
  if n <= 15:
    return (0, 1, 2, 3, 4, 5, 6, 9, 12, 16, 20, 27, 36, 48, 64, 81)[n]
  e3 = (4 - n) % 5
  e4 = n // 5 - e3
  return 4 * (4 ** e4) * (3 ** e3)

Cálculo de e3: Siempre hay entre 0 y 4 patrones SCPP al final de la lista de pulsaciones de teclas, porn % 5 == 4 hay 4, n % 5 == 1hay 3, n % 5 == 2hay 2, n % 5 == 3hay 1 y n % 5 == 4hay 0. Esto se puede simplificar a (4 - n) % 5.

Cálculo de e4: El número total de patrones aumenta en 1 siempre que n % 5 == 0, como resultado, este número aumenta exactamente n / 5. Usando la división del piso podemos obtener el número total de patrones, el número total de e4es el número total de patrones menose3 . Para aquellos que no están familiarizados con Python, //es la notación a prueba de futuro para la división de pisos.

Así es como lo abordaría:

• asumir CtrlA= seleccionar todo
• asumir CtrlC= copiar selección
• asumir CtrlV= pegar la selección copiada

dado algo de texto, se necesitan 4 pulsaciones para duplicarlo:

• CtrlA para seleccionarlo todo
• CtrlC para copiarlo
• CtrlV para pegar (esto se pegará sobre la selección - DECLARE SUS SUPUESTOS)
• CtrlV para pegar de nuevo lo que lo duplica.

A partir de ahí, puede considerar hacer 4 o 5 A, luego recorrer lo anterior. Tenga en cuenta que hacerlo ctrl + a, c, v, vhará que su texto crezca exponencialmente a medida que lo recorra. Si los trazos restantes son <4, sigue haciendo unCtrlV

La clave para las entrevistas en lugares como Google es expresar sus suposiciones y comunicar su pensamiento. quieren saber cómo resuelves los problemas.

Se puede resolver en O (1): al igual que con los números de Fibonacci, hay una fórmula para calcular el número de As impresos (y la secuencia de pulsaciones de teclas):

1) Podemos simplificar la descripción del problema:

• Tener solo [A], [Ca] + [Cc], [Cv] y un búfer de copiar-pegar-vacío

es igual a

• teniendo solo [Ca] + [Cc], [Cv] y "A" en el búfer de copiar-pegar.

2) Podemos describir la secuencia de pulsaciones de teclas como una cadena de N caracteres de {'*', 'V', 'v'}, donde 'v' significa [Cv] y '*' significa [Ca] y 'V 'significa [Cc]. Ejemplo: "vvvv * Vvvvv * Vvvv"

La longitud de esa cuerda aún es igual a N.

El producto de las longitudes de las Vv-palabras en esa cadena es igual al número de As producidas.

3) Dada una longitud fija N para esa cadena y un número fijo K de palabras, el resultado será máximo si todas las palabras tienen casi la misma longitud. Su diferencia entre pares no es más de ± 1.

Ahora bien, ¿cuál es el número óptimo K, si se da N?

4) Supongamos que queremos aumentar el número de palabras agregando una sola palabra de longitud L, luego tenemos que reducir L + 1 veces cualquier palabra anterior en una 'v'. Ejemplo: "… * Vvvv * Vvvv * Vvvv * Vvvv" -> "… * Vvv * Vvv * Vvv * Vvv * Vvv"

Ahora, ¿cuál es la longitud de palabra óptima L?

(5 * 5 * 5 * 5 * 5) <(4 * 4 * 4 * 4 * 4) * 4, (4 * 4 * 4 * 4)> (3 * 3 * 3 * 3) * 3

=> Óptimo es L = 4.

5) Supongamos que tenemos una N suficientemente grande para generar una cadena con muchas palabras de longitud 4, pero quedan algunas pulsaciones de teclas; ¿cómo debemos usarlos?

• Si quedan 5 o más: agregue otra palabra con longitud 4.

• Si quedan 0: Listo.

• Si quedan 4: Podríamos

  a) agregue una palabra con longitud 3: 4 * 4 * 4 * 4 * 3 = 768.

  b) o aumentar 4 palabras para que tengan una longitud de 5: 5 * 5 * 5 * 5 = 625. => Es mejor agregar una palabra.

• Si quedan 3: Podríamos

  a) o agregue una palabra con longitud 3 ajustando la palabra anterior de longitud 4 a 3: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.

  b) aumenta 3 palabras para que tengan una longitud de 5: 5 * 5 * 5 = 125. => Es mejor agregar una palabra.

• Si quedan 2: Podríamos

  a) o agregue una palabra con longitud 3 ajustando las dos palabras anteriores de longitud 4 a 3: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.

  b) aumenta 2 palabras para que tengan una longitud de 5: 5 * 5 = 25. => Es mejor agregar una palabra.

• Si queda 1: Podríamos

  a) o agregue una palabra con longitud 3 ajustando las tres palabras anteriores de longitud 4 a 3: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.

  b) aumenta una palabra para que tenga una longitud de 5: 4 * 4 * 5 = 80. => Es mejor agregar una palabra.

6) Ahora, ¿qué pasa si no tenemos una "N suficientemente grande" para usar las reglas en 5)? ¡Tenemos que ceñirnos al plan b), si es posible! Las cadenas para N pequeña son:

1: "v", 2: "vv", 3: "vvv", 4: "vvvv"

5: "vvvvv" → 5 (plan b)

6: "vvvvvv" → 6 (plan b)

7: "vvv * Vvv" → 9 (plan a)

8: "vvvv * Vvv" → 12 (plan a)

9: "vvvv * Vvvv" → 16

10: "vvvv * Vvvvv" → 20 (plan b)

11: "vvv * Vvv * Vvv" → 29 (plan a)

12: "vvvv * Vvv * Vvv" → 36 (plan a)

13: "vvvv * Vvvv * Vvv" → 48 (plan a)

14: "vvvv * Vvvv * Vvvv" → 64

15: "vvv * Vvv * Vvv * Vvv" → 81 (plan a)

...

7) Ahora, ¿cuál es el número óptimo K de palabras en una cadena de longitud N?

Si N <7, entonces K = 1; de lo contrario, si 6 <N <11, entonces K = 2; de lo contrario: K = ceil ((N + 1) / 5)

Escrito en C / C ++ / Java: int K = (N<7)?(1) : (N<11)?(2) : ((N+5)/5);

Y si N> 10, entonces el número de palabras con longitud 3 será: K * 5-1-N. Con esto, podemos calcular el número de As impresos:

Si N> 10, el número de As será: 4 ^ {N + 1-4K} · 3 ^ {5K-N-1}

Usar CtrlA+ CtrlC+ CtrlVes una ventaja solo después de 4 'A's.

Entonces haría algo como esto (en código pseudo-BÁSICO, ya que no ha especificado ningún idioma adecuado):

// We should not use the clipboard for the first four A's:
FOR I IN 1 TO MIN(N, 4)
    PRINT 'CLICK A'
NEXT
LET N1 = N - 4

// Generates the maximum number of pastes allowed:
FOR I IN 1 TO (N1 DIV 3) DO
    PRINT 'CTRL-A'
    PRINT 'CTRL-C'
    PRINT 'CTRL-V'
    LET N1 = N1 - 3
NEXT

// If we still have same keystrokes left, let's use them with simple CTRL-Vs
FOR I IN N1 TO N
    PRINT 'CTRL-V'
NEXT

Editar

1. Volvamos a usar un single CtrlVen el bucle principal.
2. Se agregaron algunos comentarios para explicar lo que estoy tratando de hacer aquí.
3. Se solucionó un problema con el bloque "primeras cuatro A".

Se necesitan 3 pulsaciones para duplicar el número de As. Solo tiene sentido comenzar a duplicar cuando ya tenga 3 o más Como ya impresos. Desea que la última pulsación de tecla permitida sea a CtrlVpara asegurarse de que está duplicando el número más grande que pueda, por lo que para alinearlo, completaremos las pulsaciones de tecla adicionales después de las tres primeras As al principio con más As.

for (i = 3 + n%3; i>0 && n>0; n--, i--) {
    print("a");
}

for (; n>0; n = n-3) {
    print("ctrl-a");
    print("ctrl-c");
    print("ctrl-v");
}

Editar:

Esto es terrible, me adelanté por completo y no consideré múltiples pastas para cada copia.

Edición 2:

Creo que pegar 3 veces es óptimo, cuando tienes suficientes pulsaciones de teclas para hacerlo. Con 5 pulsaciones de tecla, multiplica su número de As por 4. Esto es mejor que multiplicar por 3 utilizando 4 pulsaciones de tecla y mejor que multiplicar por 5 utilizando 6 pulsaciones de tecla. Comparé esto dando a cada método el mismo número de pulsaciones de teclas, lo suficiente para que cada uno termine un ciclo al mismo tiempo (60), dejando que el multiplicador 3 haga 15 ciclos, el multiplicador 4 haga 12 ciclos y el multiplicador 5 el multiplicador hace 10 ciclos. 3 ^ 15 = 14.348.907, 4 ^ 12 = 16.777.216 y 5 ^ 10 = 9.765.625. Si solo quedan 4 pulsaciones de tecla, hacer un multiplicador de 3 es mejor que pegar 4 veces más, esencialmente haciendo que el multiplicador de 4 anterior se convierta en un multiplicador de 8. Si solo quedan 3 pulsaciones de teclas, lo mejor es un multiplicador de 2.

Suponga que tiene x caracteres en el portapapeles y x caracteres en el área de texto; llamémoslo "estado x".

Presionemos "Pegar" unas cuantas veces (lo denoto por m-1por conveniencia), luego "Seleccionar todo" y "Copiar"; después de esta secuencia, llegamos al "estado m * x". Aquí, desperdiciamos un total de m + 1 pulsaciones de teclas. Entonces, el crecimiento asintótico es (al menos) algo así como f^n, donde f =m^(1/(m+1)) . Creo que es el crecimiento asintótico máximo posible, aunque no puedo probarlo (todavía).

Probar varios valores de m muestra que el máximo de f se obtiene para m=4 .

Usemos el siguiente algoritmo:

Press A a few times
Press Select-all
Press Copy
Repeat a few times:
    Press Paste
    Press Paste
    Press Paste
    Press Select-all
    Press Copy
While any keystrokes left:
    Press Paste

(no estoy seguro de que sea el óptimo).

El número de veces que debe presionar A al principio es 3: si lo presiona 4 veces, pierde la oportunidad de duplicar el número de A en 3 pulsaciones más.

El número de veces que debe presionar Pegar al final no es más de 5: si le quedan 6 o más pulsaciones de teclas, puede usar Pegar, Pegar, Pegar, Seleccionar todo, Copiar, Pegar en su lugar.

Entonces, obtenemos el siguiente algoritmo:

If (less than 6 keystrokes - special case)
    While (any keystrokes left)
        A
Else
    First 5 keystrokes: A, A, A, Select-all, Copy
    While (more than 5 keystrokes left)
        Paste, Paste, Paste, Select-all, Copy
    While (any keystrokes left)
        Paste

(no estoy seguro de que sea el óptimo). La cantidad de caracteres después de ejecutar esto es algo así como

3 * pow(4, floor((n - 6) / 5)) * (2 + (n - 1) % 5).

Valores de muestra: 1,2,3,4,5,6,9,12,15,18,24,36,48,60,72,96,144,192,240,288, ...

Lo que sigue usa la segunda edición del OP que pegar no reemplaza el texto existente.

Note algunas cosas:

• ^ A y ^ C pueden considerarse una sola acción que requiere dos pulsaciones de teclas, ya que nunca tiene sentido hacerlas individualmente. De hecho, podemos reemplazar todas las instancias de ^ A ^ C con ^ K ^ V, donde ^ K es una tecla operación de "corte" de (abreviémosla X). Veremos que tratar con ^ K es mucho más agradable que con ^ A ^ C de dos costos.
• Supongamos que comienza una 'A' en el portapapeles. Entonces ^ V (abreviémoslo Y) es estrictamente superior a A y podemos descartar este último de toda consideración. (En el problema real, si el portapapeles comienza vacío, en lo que sigue reemplazaremos Y con A en lugar de ^ V hasta la primera X).

Por tanto, cada secuencia de pulsaciones de teclas razonable se puede interpretar como un grupo de Y separados por X, por ejemplo YYYXYXYYXY. Denote por V (s) el número de 'A's producidos por la secuencia s. Entonces V (nXm) = V (n) * V (m), porque X esencialmente reemplaza cada Y en m con V (n) 'A's.

El problema de copiar y pegar es, por tanto, isomórfico al siguiente problema: "utilizando m + 1 números que suman Nm, maximizan su producto". Por ejemplo, cuando N = 6, la respuesta es m = 1 y los números (2,3). 6 = 2 * 3 = V (YYXYYY) = V (AA ^ A ^ C ^ V ^ V) (o V (YYYXYY) = V (AAA ^ A ^ C ^ V).)

Podemos hacer algunas observaciones:

Para un valor fijo de m, los números a elegir son ceil( (N-m)/(m+1) )y floor( (N-m)/(m+1) )(en cualquier combinación que haga que la suma funcione; más específicamente, necesitará (N-m) % (m+1) ceilsy el resto floors). Esto es porque, para a < b,(a+1)*(b-1) >= a*b .

Desafortunadamente, no veo una manera fácil de encontrar el valor de m. Si esta fuera mi entrevista propondría dos soluciones en este punto:

Opción 1. Repetir todo lo posible m. Una n log nsolución O ( ).

Código C ++:

long long ipow(int a, int b)
{
  long long val=1;
  long long mul=a;

  while(b>0)
    {
      if(b%2)
    val *= mul;
      mul *= mul;
      b/=2;
    }
  return val;
}

long long trym(int N, int m)
{
  int floor = (N-m)/(m+1);
  int ceil = 1+floor;
  int numceils = (N-m)%(m+1);
  return ipow(floor, m+1-numceils) * ipow(ceil, numceils);
}

long long maxAs(int N)
{
  long long maxval=0;
  for(int m=0; m<N; m++)
    {
      maxval = std::max(maxval, trym(N,m));
    }
  return maxval;
}

Opción 2. Permitir mobtener valores no enteros y encontrar su valor óptimo tomando la derivada de [(N-m)/(m+1)]^mcon respecto a my resolviendo por su raíz. No existe una solución analítica, pero la raíz se puede encontrar usando, por ejemplo, el método de Newton. Luego use el piso y el techo de esa raíz para el valor de my elija el que sea mejor.

public int dp(int n) 
{
    int arr[] = new int[n];
    for (int i = 0; i < n; i++)
        arr[i] = i + 1;
    for (int i = 2; i < n - 3; i++) 
    {
        int numchars = arr[i] * 2;
        int j = i + 3;
        arr[j] = Math.max(arr[j], numchars);
        while (j < n - 1) 
        {
            numchars = numchars + arr[i];
            arr[++j] = Math.max(arr[j], numchars);
        }
    }
    return arr[n - 1];
}

Aquí está mi enfoque y solución con el código a continuación.

Acercarse:

Hay tres operaciones distintas que se pueden realizar.

1. Pulsación de tecla A : genera un carácter 'A'
2. Pulsación de tecla (Ctrl-A) + (Ctrl-C) : no genera esencialmente nada. Estas dos pulsaciones de teclas se pueden combinar en una sola operación porque cada una de estas pulsaciones de teclas individualmente no tiene sentido. Además, esta pulsación de tecla configura la salida para la siguiente operación de pegado.
3. Pulsación de tecla (Ctrl-V) : la salida para esta pulsación de tecla realmente depende de la operación anterior (segunda) y, por lo tanto, tendríamos que tener en cuenta eso en nuestro código.

Ahora, dadas las tres operaciones distintas y sus respectivos resultados, tenemos que ejecutar todas las permutaciones de estas operaciones.

Suposición:

Ahora, alguna versión de este problema establece que la secuencia de pulsaciones de teclas, Ctrl + A -> Ctrl + C -> Ctrl + V, sobrescribe la selección resaltada. Para tener en cuenta esta suposición, solo se debe agregar una línea de código a la solución a continuación donde la variable impresa en el caso 2 se establece en 0

        case 2:
        //Ctrl-A and then Ctrl-C
            if((count+2) < maxKeys)
            {
                pOutput = printed;

                //comment the below statement to NOT factor 
                //in the assumption described above
                printed = 0;    
            }

Para esta solución

El siguiente código imprimirá un par de secuencias y la última secuencia es la respuesta correcta para cualquier N. por ejemplo, para N = 11 esta será la secuencia correcta

Con la suposición

A, A, A, A, A, C, S, V, V, V, V,: 20:

Sin la suposición

A, A, A, C, S, V, V, C, S, V, V,: 27:

He decidido mantener la suposición para esta solución.

Leyenda de pulsaciones de teclas:

'A' - A

'C' - Ctrl + A

'S' - Ctrl + C

'V' - Ctrl + V

Código:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void maxAprinted(int count, int maxKeys, int op, int printed, int pOutput, int *maxPrinted, char *seqArray)
{
    if(count > maxKeys)
        return;

    if(count == maxKeys)
    {
        if((*maxPrinted) < printed)
        {
            //new sequence found which is an improvement over last sequence
            (*maxPrinted) = printed;

            printf("\n");
            int i;
            for(i=0; i<maxKeys; i++)
                printf(" %c,",seqArray[i]);
        }

        return;
    }

    switch(op)
    {
        case 1:
        //A keystroke
            printed++;

            seqArray[count] = 'A';
            count++;
            break;

        case 2:
        //Ctrl-A and then Ctrl-C
            if((count+2) < maxKeys)
            {
                pOutput = printed;

                //comment the below statement to NOT factor 
                //in the assumption described above
                printed = 0;    
            }

            seqArray[count] = 'C';
            count++;
            seqArray[count] = 'S';
            count++;
            break;

        case 3:
        //Ctrl-V
            printed = printed + pOutput;

            seqArray[count] = 'V';
            count++;
            break;
    }

    maxAprinted(count, maxKeys, 1, printed, pOutput, maxPrinted, seqArray);
    maxAprinted(count, maxKeys, 2, printed, pOutput, maxPrinted, seqArray);
    maxAprinted(count, maxKeys, 3, printed, pOutput, maxPrinted, seqArray);    
}

int main()
{
    const int keyStrokes = 11;

    //this array stores the sequence of keystrokes
    char *sequence;
    sequence = (char*)malloc(sizeof(char)*(keyStrokes + 1));

    //stores the max count for As printed for a sqeuence
    //updated in the recursive call.
    int printedAs = 0;

    maxAprinted(0, keyStrokes,  1, 0, 0, &printedAs, sequence);

    printf(" :%d:", printedAs);

    return 0;
}    

Usando los trucos mencionados en las respuestas anteriores, Matemáticamente, la Solución se puede explicar en una ecuación como,

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5]. donde [] es el mayor factor entero

Existe una compensación entre imprimir mA manualmente y luego usar Ctrl+ A, Ctrl+ Cy Nm-2 Ctrl+V . La mejor solución está en el medio. Si el número máximo de pulsaciones de tecla = 10, la mejor solución es escribir 5 A o 4 A.

intente usar esto Mire esto http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ y tal vez optimice un poco buscando los resultados en la mitad punto.

Aquí está mi solución con programación dinámica, sin un ciclo anidado, y que también imprime los caracteres reales que necesitaría escribir:

N = 52

count = [0] * N
res = [[]] * N
clipboard = [0] * N

def maybe_update(i, new_count, new_res, new_clipboard):
  if new_count > count[i] or (
      new_count == count[i] and new_clipboard > clipboard[i]):
    count[i] = new_count
    res[i] = new_res
    clipboard[i] = new_clipboard

for i in range(1, N):
  # First option: type 'A'.
  # Using list concatenation for 'res' to avoid O(n^2) string concatenation.
  maybe_update(i, count[i - 1] + 1, res[i - 1] + ['A'], clipboard[i - 1])

  # Second option: type 'CTRL+V'.
  maybe_update(i, count[i - 1] + clipboard[i - 1],  res[i - 1] + ['v'],
               clipboard[i - 1])

  # Third option: type 'CTRL+A, CTRL+C, CTRL+V'.
  # Assumption: CTRL+V always appends.
  if i >= 3:
    maybe_update(i, 2 * count[i - 3],  res[i - 3] + ['acv'], count[i - 3])

for i in range(N):
  print '%2d %7d %6d %-52s' % (i, count[i], clipboard[i], ''.join(res[i]))

Esta es la salida ('a' significa 'CTRL + A', etc.)

 0       0      0                                                     
 1       1      0 A                                                   
 2       2      0 AA                                                  
 3       3      0 AAA                                                 
 4       4      0 AAAA                                                
 5       5      0 AAAAA                                               
 6       6      3 AAAacv                                              
 7       9      3 AAAacvv                                             
 8      12      3 AAAacvvv                                            
 9      15      3 AAAacvvvv                                           
10      18      9 AAAacvvacv                                          
11      27      9 AAAacvvacvv                                         
12      36      9 AAAacvvacvvv                                        
13      45      9 AAAacvvacvvvv                                       
14      54     27 AAAacvvacvvacv                                      
15      81     27 AAAacvvacvvacvv                                     
16     108     27 AAAacvvacvvacvvv                                    
17     135     27 AAAacvvacvvacvvvv                                   
18     162     81 AAAacvvacvvacvvacv                                  
19     243     81 AAAacvvacvvacvvacvv                                 
20     324     81 AAAacvvacvvacvvacvvv                                
21     405     81 AAAacvvacvvacvvacvvvv                               
22     486    243 AAAacvvacvvacvvacvvacv                              
23     729    243 AAAacvvacvvacvvacvvacvv                             
24     972    243 AAAacvvacvvacvvacvvacvvv                            
25    1215    243 AAAacvvacvvacvvacvvacvvvv                           
26    1458    729 AAAacvvacvvacvvacvvacvvacv                          
27    2187    729 AAAacvvacvvacvvacvvacvvacvv                         
28    2916    729 AAAacvvacvvacvvacvvacvvacvvv                        
29    3645    729 AAAacvvacvvacvvacvvacvvacvvvv                       
30    4374   2187 AAAacvvacvvacvvacvvacvvacvvacv                      
31    6561   2187 AAAacvvacvvacvvacvvacvvacvvacvv                     
32    8748   2187 AAAacvvacvvacvvacvvacvvacvvacvvv                    
33   10935   2187 AAAacvvacvvacvvacvvacvvacvvacvvvv                   
34   13122   6561 AAAacvvacvvacvvacvvacvvacvvacvvacv                  
35   19683   6561 AAAacvvacvvacvvacvvacvvacvvacvvacvv                 
36   26244   6561 AAAacvvacvvacvvacvvacvvacvvacvvacvvv                
37   32805   6561 AAAacvvacvvacvvacvvacvvacvvacvvacvvvv               
38   39366  19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacv              
39   59049  19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvv             
40   78732  19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvv            
41   98415  19683 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvvv           
42  118098  59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacv          
43  177147  59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvv         
44  236196  59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvv        
45  295245  59049 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvvv       
46  354294 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacv      
47  531441 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvv     
48  708588 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvv    
49  885735 177147 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvvv   
50 1062882 531441 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacv  
51 1594323 531441 AAAacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvvacvv 

Si se permiten N pulsaciones de tecla, el resultado es N-3.

A's -> N-3

CTRL+A -> Seleccionando esos N caracteres: +1

CTRL+ C-> Copiando esos N caracteres: +1

Ctrl+ V-> Pegar los N caracteres. : +1 es decir, (ya que hemos seleccionado todos los caracteres usando CTRL+ A) Reemplazando estos N-3 caracteres existentes con los N-3 caracteres copiados (que anula los mismos caracteres) y el resultado es N-3.