Nombre maximal de caractères à l’aide des touches A, Ctrl + A, Ctrl + C et Ctrl + V

Question

C'est une question d'entrevue à partir de google. Je ne suis pas en mesure de le résoudre par moi-même. Quelqu'un peut-il éclairer?

Écrire un programme pour imprimer la séquence de frappes de touches telles que génère le nombre maximum de caractère". Vous êtes autorisé à utiliser seulement 4 touches: A, Ctrl+A, Ctrl+C et Ctrl+V. Seulement N frappes de touche sont autorisés. Toutes les touches Ctrl+ caractères sont considérés comme une combinaison de touches, donc Ctrl+A est une séquence de touches.

Par exemple, la séquence A, Ctrl+A, Ctrl+C, Ctrl+V génère deux Un 4 touches.

• Ctrl+A Sélectionner Tout
• Ctrl+C Copier
• Ctrl+V Coller

J'ai fait un peu de mathématiques. Pour tout N, en utilisant des nombres de x de A , de l'un Ctrl+A, un Ctrl+C et y Ctrl+V, nous pouvons générer max ((N-1)/2)² nombre de Un. Pour N > M, il est préférable d'utiliser Ctrl+A, Ctrl+C et Ctrl+V séquences comme il double le nombre de Un.

La séquence Ctrl+A, Ctrl+V, Ctrl+C ne va pas de remplacer la sélection existante. Il va ajouter la sélection copiée de celle sélectionnée.

Answer 1

Il y a une dynamique de la solution de programmation. Nous commençons par savoir 0 touches de nous faire 0. Puis nous parcourir pour i jusqu'à n, faisant deux choses: en appuyant Une fois et en appuyant sur select + copie suivie par la pâte j temps (en fait, j-i-1 - dessous; note l'astuce ici: le contenu est toujours dans le presse-papiers, de sorte que nous pouvons coller plusieurs fois sans avoir à les copier à chaque fois). Nous n'avons qu'à considérer jusqu'à 4 fois de suite pâtes, depuis sélectionner, copier, coller x 5 est équivalent à sélectionner, copier, coller, sélectionner, copier, coller et celle-ci est mieux car il nous laisse avec plus de dans le presse-papiers. Une fois que nous avons atteint n, nous avons le résultat souhaité.

La complexité semble être O(N), mais le nombre de croître à un rythme exponentiel, il est en fait en O(N²) en raison de la complexité de la multiplication de grands nombres. Ci-dessous est un Python de mise en œuvre. Il faut environ 0,5 secondes à calculer pour N=50 000 habitants.

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]

Dans le code, j représente le nombre total de touches enfoncées après notre nouvelle séquence de touches. Nous avons déjà i des combinaisons de touches à ce stade, et 2 nouvelles pressions sur les touches aller à sélectionner tout et copier. Par conséquent, nous sommes frapper pâte j-i-2 temps. Depuis collage ajoute à l'existant séquence de dp[i] As', nous avons besoin d'ajouter 1 rendre j-i-1. C'est ce qui explique l' j-i-1 dans la 2e à la dernière ligne.

Voici quelques résultats (n => nombre d'):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• De 1 000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• De 50 000 => un très grand nombre!

Je suis d'accord avec @SB que vous devez toujours l'état de vos hypothèses: le Mien, c'est que vous n'avez pas besoin de coller deux fois de doubler le nombre de caractères. Il obtient la réponse pour 7, de sorte que si ma solution est fausse, l'hypothèse doit être droit.

Dans le cas où quelqu'un se demande pourquoi je ne suis pas la vérification des séquences de la forme Ctrl+A, Ctrl+C, A, Ctrl+V: Le résultat final sera toujours le même comme Une, Ctrl+A, Ctrl+C, Ctrl+V , qui, je dois prendre en compte.

Answer 2

En utilisant marcog la solution que j'ai trouvé un modèle qui commence à n=16. Pour illustrer cela, voici les séquences de touches pour n=24 jusqu'à n=29, j'ai remplacé ^) avec S (sélectionner), ^C, avec C (copier), et ^V avec P (coller) pour plus de lisibilité:

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

Après une période initiale de 4, le modèle idéal est de sélectionner, copier, coller, coller, coller et répétez. Cela permettra de multiplier le nombre de Que par 4 tous les 5 touches. Si cette 5 de frappe modèle ne peut pas consommer le reste des frappes sur son propre certains nombre de 4 modèles de frappe (SCPP) consomment de la finale de frappes, en remplacement de SCPPP (ou enlever un de la colle si nécessaire. Les 4 touches modèles de multiplier le total par 3 toutes les 4 touches.

L'utilisation de ce modèle, voici de code Python qui obtient les mêmes résultats que marcog de la solution, mais est O(1) edit: C'est en fait en O(log n) en raison de l'exponentiation, grâce à IVlad pour le pointage.

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)

Le calcul de l'e3: Il y a toujours entre 0 et 4, la SCPP modèles à la fin de la liste touche, pour n % 5 == 4 il y a 4, n % 5 == 1 y sont de 3, n % 5 == 2 il y a 2, n % 5 == 3 il y a 1, et n % 5 == 4 il y a 0. Cela peut être simplifié à l' (4 - n) % 5.

Le calcul e4: Le nombre total de modèles augmente de 1 à chaque fois qu' n % 5 == 0, il s'avère que ce nombre augmente à exactement n / 5. À l'aide de chaussée de la division, nous pouvons obtenir le nombre total de motifs, le nombre total de e4 le nombre total de modèles de moins e3. Pour ceux qui ne connaissent Python, // est l'avenir de la notation pour le plancher de la division.

Answer 3

Voici comment je pourrais l'aborder:

• supposons CtrlA = sélectionner tout
• supposons CtrlC = copier la sélection
• supposons CtrlV = coller sélection copiée

compte tenu du peu de texte, il faut 4 touches pour le dupliquer:

• CtrlA pour sélectionner tout
• CtrlC pour copier
• CtrlV pour coller (cela va coller sur la sélection à l'ÉTAT d'HYPOTHÈSES)
• CtrlV pour coller à nouveau ce qui le double.

À partir de là, vous pouvez envisager de faire 4 ou 5, puis une boucle sur le dessus. Notez que cette opération ctrl + a, c, v, v augmentera votre texte de façon exponentielle en boucle. Si les traits restants < 4, continuez juste de faire un CtrlV

La clé pour des entrevues @ endroits tels que Google est à l'état de vos hypothèses, et de communiquer votre façon de penser. ils veulent savoir comment résoudre des problèmes.

Answer 4

À l'aide de CtrlA + CtrlC + CtrlV est un avantage seulement après 4'.

Donc, je voudrais faire quelque chose comme ceci (en pseudo-BASE de code, puisque vous n'avez pas précisé de quelle langue):

// 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

Modifier

1. Retour à l'aide d'une seule touche CtrlV dans la boucle principale.
2. Ajouté des commentaires pour expliquer ce que j'essaie de faire ici.
3. Correction d'un problème avec le "premier quatre Un" bloc.

Answer 5

C'est solveable en O(1): Comme avec les nombres de Fibonacci, il existe une formule pour calculer le nombre d'impressions Que (et la séquence de frappes de touches):

---

1) Nous pouvons simplifier la description du problème:

• Le fait d'avoir seulement [A],[C-a]+[C-c],[C-v] et un vide de copier-coller le tampon

est égal à

• le fait d'avoir seulement [C-a]+[C-c],[C-v] et "A" dans le copier-coller-tampon.

---

2), Nous pouvons décrire la séquence de frappes de touches comme une chaîne de N caractères de {'*','V','v'}, où le " v "signifie [C-v] et" * "signifie [C-a] et" V " signifie [C-c]. Exemple: "vvvv*Vvvvv*Vvvv"

La longueur de cette chaîne est égale à N.

Le produit de la longueur de la Vv-mots dans cette chaîne est égale à la quantité de produit Que.

---

3) compte tenu d'une longueur fixe N de cette chaîne et d'un nombre fixe K de mots, le résultat sera maximal ssi tous les mots ont presque la même longueur. Leur paire, la différence n'est pas de plus de ±1.

Maintenant, quel est le nombre optimal K, si N est-il donné?

---

4) Supposons que, nous voulons augmenter le nombre de mots en ajoutant un seul mot de longueur L, alors nous devons réduire L+1 fois tout mot précédent par un "v". Exemple: "...*Vvvv*Vvvv*Vvvv*Vvvv" -> "...*Vvv*Vvv*Vvv*Vvv*Vvv"

Maintenant, quel est le meilleur mot de longueur L?

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

=> L'idéal, c'est L=4.

---

5) Supposons, nous avons suffisamment grand N pour générer une chaîne de caractères avec beaucoup de mots de longueur 4, mais quelques touches de gauche; comment doit-on utiliser?

• Si il y a 5 ou plus à gauche: Ajouter un autre mot avec une longueur de 4.

• Si il y a des 0 à gauche: Fait.

• Si il y a 4 gauche: On peut soit

  a) ajouter un mot de longueur 3: 4*4*4*4*3=768.

  b) ou une augmentation de 4 mots de longueur 5: 5*5*5*5=625. => En ajoutant un mot, c'est mieux.

• Si il y a 3 gauche: On peut soit

  a) ou d'ajouter un mot de longueur 3 en ajustant la previus mot à partir d'une longueur de 4 à 3: 4*4*4*2=128 < 4*4*3*3=144.

  b) augmenter de 3 mots de longueur 5: 5*5*5=125. => En ajoutant un mot, c'est mieux.

• Si il y a 2 gauche: On peut soit

  a) ou d'ajouter un mot de longueur 3 en ajustant la previus deux mots de longueur 4 à 3: 4*4*1=16 < 3*3*3=27.

  b) augmentation de 2 mots de longueur 5: 5*5=25. => En ajoutant un mot, c'est mieux.

• Si il y a 1 gauche: On peut soit

  a) ou d'ajouter un mot de longueur 3 en ajustant la previus trois mots à partir d'une longueur de 4 à 3: 4*4*4*0=0 < 3*3*3*3=81.

  b) augmenter un mot de longueur 5: 4*4*5=80. => En ajoutant un mot, c'est mieux.

---

6) Maintenant, si nous n'avons pas été "suffisamment grand N" utiliser les règles à 5)? Nous avoir à coller avec le plan b), si possible! Les cordes pour les petits N sont:

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

5:"vvvvv" → 5 (plan b)

6:"vvvvvv" → 6 (plan b)

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

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

9:"vvvv*Vvvv" → 16

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

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

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

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

14:"vvvv*Vvvv*Vvvv" → 64

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

...

---

7) Maintenant, quel est le nombre optimal K de mots dans une chaîne de longueur N?

Si N < 7 alors K=1 sinon si 6 < N < 11 K=2 ; sinon: K=ceil((N+1)/5)

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

Et si N > 10, puis le nombre de mots de longueur 3: K*5-1-N. Avec cela, nous pouvons calculer le nombre de documents imprimés:

Si N > 10, le nombre de Comme sera: 4^{N+1-4K}·3^{5K-N-1}