Número máximo de caracteres usando as teclas A, Ctrl + A, Ctrl + C e Ctrl + V

Esta é uma pergunta da entrevista do google. Eu não sou capaz de resolver sozinho. Alguém pode lançar alguma luz?

Escreva um programa para imprimir a sequência de pressionamentos de tecla de forma que gere o número máximo de caracteres 'A's. Você está autorizado a usar apenas 4 teclas: A, Ctrl+ A, Ctrl+ Ce Ctrl+ V. Apenas N pressionamentos de tecla são permitidos. Todos os Ctrlcaracteres + são considerados como um toque de tecla, portanto Ctrl+ Aé um toque de tecla.

Por exemplo, a sequência de A, Ctrl+ A, Ctrl+ C, Ctrl+ Vgera dois de um em 4 batidas de tecla.

• Ctrl + A é Selecionar Tudo
• Ctrl + C é Copiar
• Ctrl + V é colar

Eu fiz matemática. Para qualquer N, usando x números de A's, um Ctrl+ A, um Ctrl+ Cey Ctrl+ V, podemos gerar max ((N-1) / 2) ² números de A's. Para alguns N> M, é melhor usar tantas sequências Ctrl+ A's, Ctrl+ Ce Ctrl+ Vquanto dobra o número de A's.

A sequência Ctrl+ A, Ctrl+ V, Ctrl+ Cnão substituirá a seleção existente. Isso acrescentará a seleção copiada à selecionada.

Existe uma solução de programação dinâmica. Começamos sabendo que 0 chaves podem nos tornar 0 A's. Em seguida, iteramos por iaté n, fazendo duas coisas: pressionando A uma vez e pressionando selecionar tudo + copiar seguido por jtempos de colar (na verdade j-i-1abaixo; observe o truque aqui: o conteúdo ainda está na área de transferência, então podemos colá-lo várias vezes sem copiando cada vez). Só temos que considerar até 4 pastas consecutivas, pois selecionar, copiar, colar x 5 equivale a selecionar, copiar, colar, selecionar, copiar, colar e esta última é melhor porque nos deixa com mais na área de transferência. Assim que chegarmos n, teremos o resultado desejado.

A complexidade pode parecer O (N), mas como os números crescem a uma taxa exponencial, é na verdade O (N ² ) devido à complexidade de multiplicar os grandes números. Abaixo está uma implementação Python. Leva cerca de 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]

No código, jrepresenta o número total de teclas pressionadas após nossa nova sequência de pressionamentos de tecla. Já temos ipressionamentos de tecla neste estágio, e 2 novos pressionamentos de tecla vão para selecionar tudo e copiar. Portanto, estamos batendo j-i-2tempos de colar . Uma vez que colar adiciona à sequência existente de dp[i] A's, precisamos adicionar 1make it j-i-1. Isso explica o j-i-1na penúltima linha.

Aqui estão alguns resultados ( n=> número de A's):

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

Concordo com @SB que você deve sempre declarar suas suposições: A minha é que você não precisa colar duas vezes para dobrar o número de caracteres. Isso obtém a resposta 7, portanto, a menos que minha solução esteja errada, a suposição deve estar certa.

No caso de alguém se pergunta por que eu não estou verificando seqüências de forma Ctrl+ A, Ctrl+ C, A, Ctrl+ V: O resultado final será sempre a mesma A, Ctrl+ A, Ctrl+ C, Ctrl+ Vque eu não considerar.

Usando a solução de Marcog, encontrei um padrão que começa em n=16. Para ilustrar isso, aqui estão as combinações de teclas para n=24até n=29, substituí ^ A por S (selecionar), ^ C por C (copiar) e ^ V por P (colar) para facilitar a leitura:

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

Após 4 As iniciais, o padrão ideal é selecionar, copiar, colar, colar, colar e repetir. Isso multiplicará o número de As por 4 a cada 5 pressionamentos de tecla. Se este padrão de 5 pressionamentos de tecla não puder consumir os pressionamentos de tecla restantes por conta própria, algum número de 4 padrões de pressionamento de tecla (SCPP) consumirá os pressionamentos de tecla finais, substituindo SCPPP (ou removendo uma das pastas) conforme necessário. Os 4 padrões de pressionamento de tecla multiplicam o total por 3 a cada 4 pressionamentos de tecla.

Usando esse padrão aqui está algum código Python que obtém os mesmos resultados da solução de marcog, mas é O (1) edit : Na verdade, é O (log n) devido à exponenciação, graças a IVlad por apontar isso.

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)

Calculando e3: Sempre há entre 0 e 4 padrões SCPP no final da lista de pressionamentos de tecla, pois n % 5 == 4há 4, n % 5 == 1há 3, n % 5 == 2há 2, n % 5 == 3há 1 e n % 5 == 4há 0. Isso pode ser simplificado para (4 - n) % 5.

Calculando e4: O número total de padrões aumenta em 1 sempre n % 5 == 0que acontece que esse número aumenta exatamente n / 5. Usando a divisão de piso, podemos obter o número total de padrões, o número total de e4é o número total de padrões menos e3. Para quem não //está familiarizado com Python, é a notação preparada para o futuro para divisão de pisos.

Aqui está como eu abordaria isso:

• assumir CtrlA= selecionar tudo
• assume CtrlC= copiar seleção
• assume CtrlV= colar seleção copiada

dado algum texto, são necessários 4 pressionamentos de tecla para duplicá-lo:

• CtrlA para selecionar tudo
• CtrlC para copiá-lo
• CtrlV para colar (isso irá colar sobre a seleção - DECLARAR SUAS ASSUNÇÕES)
• CtrlV para colar novamente, o que o duplica.

A partir daí, você pode considerar fazer 4 ou 5 A's e, em seguida, repetir o procedimento acima. Observe que isso ctrl + a, c, v, vaumentará o seu texto exponencialmente conforme você o percorre. Se os traços restantes <4, continue fazendo umCtrlV

O segredo das entrevistas em locais como o Google é expor suas suposições e comunicar seu pensamento. eles querem saber como você resolve problemas.

É solucionável em O (1): Como com os números de Fibonacci, há uma fórmula para calcular o número de As impressas (e a sequência de teclas):

1) Podemos simplificar a descrição do problema:

• Tendo apenas [A], [Ca] + [Cc], [Cv] e um buffer de copiar e colar vazio

é igual a

• tendo apenas [Ca] + [Cc], [Cv] e "A" no buffer de copiar e colar.

2) Podemos descrever a sequência de pressionamentos de tecla como uma string de N caracteres de {'*', 'V', 'v'}, onde 'v' significa [Cv] e '*' significa [Ca] e 'V 'significa [Cc]. Exemplo: "vvvv * Vvvvv * Vvvv"

O comprimento dessa corda ainda é igual a N.

O produto dos comprimentos das palavras Vv nessa string é igual ao número de As produzidas.

3) Dado um comprimento fixo N para aquela string e um número fixo K de palavras, o resultado será máximo se todas as palavras tiverem comprimentos quase iguais. Sua diferença entre pares não é mais do que ± 1.

Agora, qual é o número ótimo K, se N for dado?

4) Suponha que queremos aumentar o número de palavras anexando uma única palavra de comprimento L, então temos que reduzir L + 1 vezes qualquer palavra anterior por um 'v'. Exemplo: "… * Vvvv * Vvvv * Vvvv * Vvvv" -> "… * Vvv * Vvv * Vvv * Vvv * Vvv"

Agora, qual é o comprimento ideal da palavra L?

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

=> O ideal é L = 4.

5) Suponha que temos um N grande o suficiente para gerar uma string com muitas palavras de comprimento 4, mas ainda faltam algumas teclas; como devemos usá-los?

• Se sobrar 5 ou mais: acrescente outra palavra com comprimento 4.

• Se sobrar 0: Concluído.

• Se sobrarem 4: nós poderíamos

  a) acrescente uma palavra com comprimento 3: 4 * 4 * 4 * 4 * 3 = 768.

  b) ou aumente 4 palavras para 5: 5 * 5 * 5 * 5 = 625. => Anexar uma palavra é melhor.

• Se sobrarem 3: nós poderíamos

  a) ou acrescente uma palavra com comprimento 3 ajustando a palavra anterior do comprimento 4 para 3: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.

  b) aumentar 3 palavras para 5: 5 * 5 * 5 = 125. => Anexar uma palavra é melhor.

• Se sobrarem 2: nós poderíamos

  a) ou acrescente uma palavra com comprimento 3 ajustando as duas palavras anteriores de comprimento 4 para 3: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.

  b) aumentar 2 palavras para 5: 5 * 5 = 25. => Anexar uma palavra é melhor.

• Se sobrar 1: nós poderíamos

  a) ou acrescente uma palavra com comprimento 3 ajustando as três palavras anteriores do comprimento 4 para 3: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.

  b) aumentar uma palavra para o comprimento 5: 4 * 4 * 5 = 80. => Anexar uma palavra é melhor.

6) Agora, e se não tivermos um "N grande o suficiente" para usar as regras em 5)? Temos que seguir o plano b), se possível! As strings para N pequeno são:

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

5: "vvvvv" → 5 (plano b)

6: "vvvvvv" → 6 (plano b)

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

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

9: "vvvv * Vvvv" → 16

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

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

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

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

14: "vvvv * Vvvv * Vvvv" → 64

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

…

7) Agora, qual é o número ideal K de palavras em uma string de comprimento N?

Se N <7 então K = 1 senão se 6 <N <11 então K = 2; caso contrário: K = ceil ((N + 1) / 5)

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

E se N> 10, então o número de palavras com comprimento 3 será: K * 5-1-N. Com isso, podemos calcular o número de As impressas:

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

Usar CtrlA+ CtrlC+ CtrlVé uma vantagem somente após 4 'A's.

Então, eu faria algo assim (em código pseudo-BASIC, uma vez que você não especificou uma linguagem adequada):

// 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. Voltar a usar um único CtrlVno loop principal.
2. Adicionados alguns comentários para explicar o que estou tentando fazer aqui.
3. Corrigido um problema com o bloco "primeiros quatro A".

São necessários 3 pressionamentos de tecla para dobrar o número de As. Só faz sentido começar a dobrar quando você tiver 3 ou mais As já impressos. Você deseja que o último pressionamento de tecla permitido seja um CtrlVpara ter certeza de que está dobrando o maior número possível; portanto, para alinhá-lo, preencheremos quaisquer pressionamentos de tecla extras após os primeiros três As no início com mais 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:

Isso é terrível, eu me precipitei completamente e não considerei várias pastas para cada cópia.

Editar 2:

Acredito que colar 3 vezes é o ideal, quando você tem teclas suficientes para fazê-lo. Em 5 pressionamentos de tecla, você multiplica seu número de As por 4. Isso é melhor do que multiplicar por 3 usando 4 pressionamentos de tecla e melhor do que multiplicar por 5 usando 6 pressionamentos de tecla. Eu comparei isso dando a cada método o mesmo número de pressionamentos de tecla, o suficiente para que cada um terminasse um ciclo ao mesmo tempo (60), deixando o multiplicador 3 fazer 15 ciclos, o multiplicador 4 fazer 12 ciclos e o 5- multiplicador fazer 10 ciclos. 3 ^ 15 = 14.348.907, 4 ^ 12 = 16.777.216 e 5 ^ 10 = 9.765.625. Se houver apenas 4 pressionamentos de tecla restantes, fazer um multiplicador de 3 é melhor do que colar mais 4 vezes, essencialmente fazendo com que o multiplicador 4 anterior se torne um multiplicador de 8. Se houver apenas 3 pressionamentos de tecla restantes, um multiplicador 2 é o melhor.

Suponha que você tenha x caracteres na área de transferência e x caracteres na área de texto; vamos chamá-lo de "estado x".

Vamos pressionar "Colar" algumas vezes (eu denoto por m-1por conveniência), depois "Selecionar tudo" e "Copiar"; após esta sequência, chegamos ao "estado m * x". Aqui, perdemos um total de m + 1 pressionamentos de tecla. Portanto, o crescimento assintótico é (pelo menos) algo como f^n, onde f = m^(1/(m+1)). Acredito que seja o máximo crescimento assintótico possível, embora (ainda) não possa provar.

Tentar vários valores de m mostra que o máximo para f é obtido para m=4.

Vamos usar o seguinte 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

(não tenho certeza se é o ideal).

O número de vezes para pressionar A no início é 3: se você pressioná-lo 4 vezes, perderá a oportunidade de dobrar o número de A em mais 3 pressionamentos de tecla.

O número de vezes para pressionar Colar no final não é mais do que 5: se você tiver 6 ou mais pressionamentos de tecla restantes, você pode usar Colar, Colar, Colar, Selecionar tudo, Copiar, Colar ao invés.

Então, temos o seguinte 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

(não tenho certeza se é o ideal). O número de caracteres após a execução é algo como

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

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

O que segue usa a segunda edição do OP de que colar não substitui o texto existente.

Observe algumas coisas:

• ^ A e ^ C podem ser considerados uma única ação que requer duas teclas, uma vez que nunca faz sentido fazê-las individualmente. Na verdade, podemos substituir todas as instâncias de ^ A ^ C por ^ K ^ V, onde ^ K é uma operação de "corte" de uma tecla (vamos abreviá-la X). Veremos que lidar com ^ K é muito mais agradável do que ^ A ^ C de dois custos.
• Vamos supor que um 'A' comece na área de transferência. Então ^ V (vamos abreviá-lo Y) é estritamente superior a A e podemos descartar este último de qualquer consideração. (No problema real, se a área de transferência começar vazia, a seguir iremos apenas substituir Y por A em vez de ^ V até o primeiro X.)

Cada sequência razoável de teclas pode ser interpretada como um grupo de Ys ​​separados por Xs, por exemplo, YYYXYXYYXY. Denote por V (s) o número de 'A's produzidos pela sequência s. Então V (nXm) = V (n) * V (m), porque X essencialmente substitui todo Y em m por V (n) 'A's.

O problema de copiar e colar é, portanto, isomórfico ao seguinte problema: "usando m + 1 números que somam Nm, maximiza seu produto." Por exemplo, quando N = 6, a resposta é m = 1 e os números (2,3). 6 = 2 * 3 = V (YYXYYY) = V (AA ^ A ^ C ^ V ^ V) (ou V (YYYXYY) = V (AAA ^ A ^ C ^ V).)

Podemos fazer algumas observações:

Para um valor fixo de m, os números a escolher são ceil( (N-m)/(m+1) )e floor( (N-m)/(m+1) )(em qualquer combinação que faça a soma funcionar; mais especificamente, você precisará (N-m) % (m+1) ceilse os demais floors). Isto porque, para a < b, (a+1)*(b-1) >= a*b.

Infelizmente, não vejo uma maneira fácil de encontrar o valor de m. Se esta fosse minha entrevista, eu proporia duas soluções neste momento:

Opção 1. Faça um loop em todos os possíveis m. Uma n log nsolução 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;
}

Opção 2. Permitir mobter valores não inteiros e encontrar seu valor ótimo tomando a derivada de [(N-m)/(m+1)]^mem relação a me resolvendo para sua raiz. Não há solução analítica, mas a raiz pode ser encontrada usando, por exemplo, o método de Newton. Em seguida, use o piso e o teto dessa raiz para o valor de me escolha o que for melhor.

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];
}

Aqui está minha abordagem e solução com o código abaixo.

Abordagem:

Existem três operações distintas que podem ser realizadas.

1. Pressionamento de tecla A - retorna um caractere 'A'
2. Pressionamento de tecla (Ctrl-A) + (Ctrl-C) - Não produz nada essencialmente. Essas duas combinações de teclas podem ser combinadas em uma operação porque cada uma dessas teclas individualmente não faz sentido. Além disso, esse pressionamento de tecla configura a saída para a próxima operação de colagem.
3. Pressionamento de tecla (Ctrl-V) - A saída para este pressionamento de tecla realmente depende da operação anterior (segunda) e, portanto, precisaríamos considerar isso em nosso código.

Agora, dadas as três operações distintas e suas respectivas saídas, temos que percorrer todas as permutações dessas operações.

Suposição:

Agora, alguma versão desse problema afirma que a sequência de pressionamentos de tecla, Ctrl + A -> Ctrl + C -> Ctrl + V, sobrescreve a seleção destacada. Para levar em consideração essa suposição, apenas uma linha de código precisa ser adicionada à solução abaixo, onde a variável impressa no caso 2 é definida como 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 solução

O código abaixo irá imprimir algumas sequências e a última sequência é a resposta correta para qualquer N. por exemplo, para N = 11 esta será a sequência correta

Com a suposição

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

Sem suposições

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

Decidi manter o pressuposto para esta solução.

Legenda das 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 os truques mencionados nas respostas acima, Matematicamente, a Solução pode ser explicada em uma equação como,

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5]. onde [] é o maior fator inteiro

Há uma compensação entre imprimir mAs manualmente e, em seguida, usar Ctrl+ A, Ctrl+ Ce Nm-2 Ctrl+ V. A melhor solução está no meio. Se o máximo de pressionamentos de tecla = 10, a melhor solução é digitar 5 As ou 4 As.

tente usar isso Veja este http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ e talvez otimize um pouco procurando os resultados em torno do meio ponto.

Aqui está minha solução com programação dinâmica, sem um loop aninhado, e que também imprime os caracteres reais que você precisa digitar:

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 é a saída ('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 

Se N toques de tecla forem permitidos, o resultado será N-3.

A's -> N-3

CTRL+ A-> Selecionando esses N caracteres: +1

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

Ctrl+ V-> Colando os N caracteres. : +1 ie, (Uma vez que selecionamos todos os caracteres usando CTRL+ A) Substituindo esses caracteres N-3 existentes pelos N-3 caracteres copiados (que está substituindo os mesmos caracteres) e o resultado é N-3.