Nombre maximum de caractères en utilisant les frappes A, Ctrl + A, Ctrl + C et Ctrl + V

Ceci est une question d’interview de google. Je ne suis pas capable de le résoudre moi-même. Quelqu’un peut-il faire la lumière?

Ecrivez un programme pour imprimer la séquence de touches de manière à générer le nombre maximum de caractères «A». Vous êtes autorisé à utiliser seulement 4 clés: A , Ctrl + A , Ctrl + C et Ctrl + V. Seuls N frappes sont autorisées. Tous les caractères Ctrl + sont considérés comme une seule touche, donc Ctrl + A est une frappe de touche.

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

  • Ctrl + A est Sélectionner tout
  • Ctrl + C est une copie
  • Ctrl + V est Coller

J’ai fait des mathématiques. Pour tout N, en utilisant les nombres x de A, un Ctrl + A , un Ctrl + C et y Ctrl + V , nous pouvons générer un maximum ((N-1) / 2) 2 nombre de A. Pour certains N> M, il est préférable d’utiliser autant de séquences Ctrl + A , Ctrl + C et Ctrl + V que de doubler le nombre de A.

La séquence Ctrl + A , Ctrl + V , Ctrl + C ne remplacera pas la sélection existante. Il appenda la sélection copiée à celle sélectionnée.

En utilisant la solution de marcog, j’ai trouvé un modèle qui commence à n=16 . Pour illustrer cela, voici les touches pour n=24 à n=29 , j’ai remplacé ^ A par S (select), ^ C par C (copy) et ^ V par P (paste) pour une meilleure 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 un premier 4 As, le modèle idéal consiste à sélectionner, copier, coller, coller, coller et répéter. Cela multipliera le nombre de As par 4 toutes les 5 frappes. Si cette séquence de 5 touches ne peut pas consumr les frappes restantes, un certain nombre de séquences de touches (SCPP) consumnt les frappes finales, en remplaçant SCPPP (ou en supprimant une des pâtes) si nécessaire. Les 4 séquences de touches multiplient le total par 3 toutes les 4 frappes.

En utilisant ce modèle, voici un code Python qui obtient les mêmes résultats que la solution de marcog, mais qui est O (1) edit : Ceci est en fait O (log n) dû à une exponentiation, grâce à IVlad.

 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) 

Calculer e3: Il y a toujours entre 0 et 4 modèles de SCPP à la fin de la liste de touches, pour n % 5 == 4 il y a 4, n % 5 == 1 il y a 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é à (4 - n) % 5 .

Calculer e4: Le nombre total de motifs augmente de 1 chaque fois que n % 5 == 0 , car il s'avère que ce nombre augmente exactement à n / 5 . En utilisant la division de sol, nous pouvons obtenir le nombre total de motifs, le nombre total de e4 étant le nombre total de motifs moins e3 . Pour ceux qui ne connaissent pas Python, // est la notation à l'épreuve du temps pour la division de sol.

Il y a une solution de programmation dynamic. Nous commençons par savoir que 0 clés peuvent nous faire 0 A. Ensuite, nous parcourons i jusqu’à n , en faisant deux choses: en appuyant sur A une fois et en appuyant sur select all + copy suivi par coller j fois (en fait ji-1 ci ji-1 dessous; notez le tour ici: le contenu est toujours dans le presse-papiers) peut le coller plusieurs fois sans copier à chaque fois). Il suffit de considérer jusqu’à 4 pâtes consécutives, puisque select, copy, paste x 5 est équivalent à sélectionner, copier, coller, sélectionner, copier, coller et que ce dernier est préférable car il nous en laisse plus dans le presse-papier. Une fois que nous avons atteint n , nous avons le résultat souhaité.

La complexité peut sembler être O (N), mais comme les nombres augmentent à un taux exponentiel, il s’agit en fait de O (N 2 ) en raison de la complexité de la multiplication des grands nombres. Vous trouverez ci-dessous une implémentation Python. Il faut environ 0,5 seconde pour calculer 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]*(ji-1)) # press select all, copy, paste x (ji-1) return dp[n] 

Dans le code, j représente le nombre total de touches pressées après notre nouvelle séquence de touches. Nous avons déjà des pressions sur les touches à ce stade et 2 nouvelles touches vont être sélectionnées et copiées. Par conséquent, nous frappons pâte ji-2 fois. Puisque le collage ajoute à la séquence existante de dp[i] A , nous devons append 1 rendant ji-1 . Ceci explique le ji-1 dans la 2ème ligne.

Voici quelques résultats ( n => nombre de A):

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

Je suis d’accord avec @SB que vous devez toujours indiquer vos hypothèses: la mienne est que vous n’avez pas besoin de coller deux fois pour doubler le nombre de caractères. Cela donne la réponse pour 7, donc à moins que ma solution soit erronée, l’hypothèse doit être correcte.

Si quelqu’un se demande pourquoi je ne vérifie pas les séquences de la forme Ctrl + A , Ctrl + C , A , Ctrl + V : Le résultat final sera toujours le même que A , Ctrl + A , Ctrl + C , Ctrl + V ce que je considère

Voici comment je l’approcherais:

  • supposer Ctrl A = sélectionner tout
  • supposons que Ctrl C = copie sélection
  • supposer que Ctrl V = coller la sélection copiée

compte tenu du texte, il faut 4 frappes pour le dupliquer:

  • Ctrl A pour tout sélectionner
  • Ctrl C pour le copier
  • Ctrl V pour coller (cela va coller sur la sélection – INDIQUEZ VOS HYPOTHÈSES)
  • Ctrl V pour coller à nouveau ce qui le double.

De là, vous pouvez envisager de faire 4 ou 5 A, puis de parcourir ce qui précède. Notez que faire ctrl + a, c, v, v fera croître votre texte de manière exponentielle lorsque vous effectuerez une boucle. S’il rest des traits <4, continuez simplement à faire un Ctrl V

La clé des entretiens @ lieux tels que Google consiste à énoncer vos hypothèses et à communiquer vos reflections. ils veulent savoir comment vous résolvez les problèmes.

Utiliser Ctrl A + Ctrl C + Ctrl V n’est un avantage qu’après 4 ‘A.

Je ferais donc quelque chose comme ça (en pseudo-BASIC-code, puisque vous n’avez pas spécifié de langue correcte):

 // 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’utilisation d’un seul Ctrl V dans la boucle principale.
  2. Ajout de quelques commentaires pour expliquer ce que j’essaie de faire ici.
  3. Correction d’un problème avec le bloc “premier quatre A”.

Il est résoluable dans O (1): Comme avec les nombres de Fibonacci, il existe une formule pour calculer le nombre de As imprimé (et la séquence de frappes):


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

  • N’ayant que [A], [Ca] + [Cc], [Cv] et un tampon de copier-coller vide

équivaut à

  • ayant seulement [Ca] + [Cc], [Cv] et “A” dans le tampon de copier-coller.

2) Nous pouvons décrire la séquence de frappes comme une chaîne de N chars sur {‘*’, ‘V’, ‘v’}, où ‘v’ signifie [Cv] et ‘*’ signifie [Ca] et ‘V ‘signifie [Cc]. Exemple: “vvvv * Vvvvv * Vvvv”

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

Le produit des longueurs des mots Vv dans cette chaîne est égal au nombre de As produits.


3) Étant donné une longueur fixe N pour cette chaîne et un nombre fixe de mots K, le résultat sera maximal si tous les mots ont des longueurs presque égales. Leur différence par paire n’est pas supérieure à ± 1.

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


4) Supposons que nous voulions 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, quelle est la longueur de mot optimale L?

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

=> Optimal est L = 4.


5) Supposons que nous ayons un N suffisamment grand pour générer une chaîne avec beaucoup de mots de longueur 4, mais qu’il rest quelques frappes; comment devrions-nous les utiliser?

  • S’il en rest 5 ou plus: Ajoutez un autre mot de longueur 4.

  • S’il y a 0 restant: Fait.

  • S’il en rest 4: on pourrait soit

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

    b) ou augmenter de 4 mots à 5: 5 * 5 * 5 * 5 = 625. => Ajouter un mot, c’est mieux.

  • S’il en rest 3: on pourrait soit

    a) ou ajoutez un mot de longueur 3 en ajustant le mot previus de longueur 4 à 3: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.

    b) augmenter de 3 mots à 5: 5 * 5 * 5 = 125. => Ajouter un mot, c’est mieux.

  • S’il en rest 2: on pourrait soit

    a) ou append un mot de longueur 3 en ajustant le prévius de deux mots de longueur 4 à 3: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.

    b) augmenter de 2 mots à 5: 5 * 5 = 25. => Ajouter un mot, c’est mieux.

  • S’il en rest 1: on pourrait soit

    a) ou ajoutez un mot de longueur 3 en ajustant le prévius de trois mots de longueur 4 à 3: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.

    b) augmenter un mot à la longueur 5: 4 * 4 * 5 = 80. => Ajouter un mot, c’est mieux.


6) Maintenant, que se passe-t-il si nous ne disposons pas d’un “N suffisamment grand” pour utiliser les règles du 5)? Nous devons nous en tenir au plan b), si possible! Les chaînes pour N petit sont:

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) 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 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, alors le nombre de mots de longueur 3 sera: K * 5-1-N. Avec cela, nous pouvons calculer le nombre de As imprimé:

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

Il faut 3 frappes au clavier pour doubler votre nombre de As. Il est logique de commencer à doubler lorsque vous en avez 3 ou plus. Vous voulez que votre dernière frappe au clavier soit un Ctrl V pour vous assurer de doubler le plus grand nombre possible, afin de l’aligner, nous remplirons toutes les frappes supplémentaires après les trois premiers As au début avec plus de 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"); } 

Modifier:

C’est terrible, j’ai complètement pris de l’avance sur moi-même et n’ai pas considéré plusieurs pâtes pour chaque copie.

Edit 2:

Je crois que coller 3 fois est optimal lorsque vous avez suffisamment de frappes pour le faire. En 5 frappes, vous multipliez votre nombre de As par 4. Cela vaut mieux que de multiplier par 3 en utilisant 4 frappes de touches et mieux que de multiplier par 5 en utilisant 6 frappes de touches. J’ai comparé cela en donnant à chaque méthode le même nombre de frappes, assez pour que chacun termine un cycle en même temps (60), laissant le 3-multiplicateur faire 15 cycles, le multiplicateur 4 faire 12 cycles et le 5 multiplicateur faire 10 cycles. 3 ^ 15 = 14 348 907, 4 ^ 12 = 16 777 216 et 5 ^ 10 = 9 765 625. S’il ne rest que 4 frappes au clavier, faire un multiplicateur de 3 est préférable à coller 4 fois de plus, ce qui fait que le multiplicateur 4 précédent devient un multiplicateur de 8. S’il ne rest plus que 3 frappes, un multiplicateur de 2 est préférable.

Supposons que vous avez x caractères dans le presse-papiers et x caractères dans la zone de texte; appelons-le “état x”.

Appuyez sur “Coller” quelques fois (je le dénote par m-1 pour plus de commodité), puis “Tout sélectionner” et “Copier”; après cette séquence, on arrive à “state m * x”. Ici, nous avons perdu un total de m + 1 frappes au clavier. Donc, la croissance asymptotique est (au moins) quelque chose comme f^n , où f = m^(1/(m+1)) . Je crois que c’est la croissance asymptotique maximale possible, bien que je ne puisse pas encore le prouver.

Essayer différentes valeurs de m montre que le maximum pour f est obtenu pour m=4 .

Utilisons l’algorithme suivant:

 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 

(pas sûr que ce soit optimal).

Le nombre de fois que vous appuyez sur A au début est de 3: si vous appuyez 4 fois sur cette touche, vous perdez l’opportunité de doubler le nombre de A dans 3 autres frappes.

Le nombre de fois que vous appuyez sur Coller à la fin n’est pas supérieur à 5: si vous avez 6 touches ou plus à gauche, vous pouvez utiliser Coller, Coller, Coller, Tout sélectionner, Copier, Coller.

Ainsi, nous obtenons l’algorithme suivant:

 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 

(pas sûr que ce soit optimal). Le nombre de caractères après l’exécution est quelque chose comme

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

Valeurs de l’échantillon: 1,2,3,4,5,6,9,12,15,18,24,36,48,60,72,96,144,192,240,288, …

Ce qui suit utilise la deuxième édition du PO pour que le collage ne remplace pas le texte existant.

Notez quelques choses:

  • ^ A et ^ C peuvent être considérés comme une seule action nécessitant deux frappes de touches, car cela n’a jamais de sens de les faire individuellement. En fait, nous pouvons remplacer toutes les instances de ^ A ^ C par ^ K ^ V, où ^ K est une opération “coupée” à une touche (abrégons-le X). Nous verrons que traiter avec ^ K est beaucoup plus intéressant que le double coût ^ A ^ C.
  • Supposons qu’un ‘A’ commence dans le presse-papiers. Alors ^ V (l’abréviation Y) est ssortingctement supérieur à A et on peut laisser tomber ce dernier de toute considération. (Dans le problème actuel, si le presse-papier démarre vide, dans ce qui suit nous remplacerons simplement Y par A au lieu de ^ V jusqu’au premier X.)

Chaque séquence de frappe raisonnable peut donc être interprétée comme un groupe de Y séparés par des X, par exemple YYYXYXYYXY. Notons V (s) le nombre de ‘A produit par la séquence s. Alors V (nXm) = V (n) * V (m), parce que X remplace essentiellement tous les Y de m par V (n) ‘A.

Le problème de copier-coller est donc isomorphe au problème suivant: “utiliser des nombres m + 1 qui totalisent Nm, maximiser leur produit.” Par exemple, lorsque N = 6, la réponse est m = 1 et les nombres (2,3). 6 = 2 * 3 = V (YYXYYY) = V (AA ^ A ^ C ^ V ^ V) (ou V (YYYXYY) = V (AAA ^ A ^ C ^ V).)

Nous pouvons faire quelques observations:

Pour une valeur fixe de m , les nombres à choisir sont ceil( (Nm)/(m+1) ) et le floor( (Nm)/(m+1) ) (quelle que soit la combinaison qui fait la sum, plus précisément vous aura besoin de (Nm) % (m+1) ceils et des floor repos. En effet, pour a < b , (a+1)*(b-1) >= a*b .

Malheureusement, je ne vois pas de moyen facile de trouver la valeur de m . Si c'était mon entretien, je proposerais deux solutions à ce stade:

Option 1. Boucle sur tous les m possibles. Une solution O ( n log n ).

Code 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 = (Nm)/(m+1); int ceil = 1+floor; int numceils = (Nm)%(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 

Option 2. Autoriser m à atteindre des valeurs non entières et à trouver sa valeur optimale en prenant la dérivée de [(Nm)/(m+1)]^m par rapport à m et en résolvant pour sa racine. Il n'y a pas de solution analytique, mais la racine peut être trouvée en utilisant par exemple la méthode de Newton. Utilisez ensuite le plancher et le plafond de cette racine pour la valeur de m et choisissez celui qui convient le mieux.

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

Voici mon approche et solution avec le code ci-dessous.

Approche:

Trois opérations distinctes peuvent être effectuées.

  1. Séquence de touches A – Émet un caractère ‘A’
  2. Séquence de touches (Ctrl-A) + (Ctrl-C) – N’émet rien essentiellement. Ces deux frappes peuvent être combinées en une seule opération car chacune de ces frappes individuelles n’a aucun sens. En outre, cette frappe définit la sortie pour la prochaine opération de collage.
  3. Séquence de touches (Ctrl-V) – La sortie pour cette frappe dépend vraiment de la (seconde) opération précédente et nous devrions donc en tenir compte dans notre code.

Maintenant, étant donné les trois opérations distinctes et leurs résultats respectifs, nous devons parcourir toutes les permutations de ces opérations.


Supposition:

Maintenant, une version de ce problème indique que la séquence de frappes au clavier, Ctrl + A -> Ctrl + C -> Ctrl + V, écrase la sélection en surbrillance. Pour tenir compte de cette hypothèse, une seule ligne de code doit être ajoutée à la solution ci-dessous, où la variable imprimée dans le cas 2 est définie sur 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; } 

Pour cette solution

Le code ci-dessous imprimera quelques séquences et la dernière séquence est la réponse correcte pour tout N. donné. Par exemple, pour N = 11, ce sera la séquence correcte

Avec l'hypothèse

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

Sans l'hypothèse

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

J'ai décidé de conserver l'hypothèse pour cette solution.


Légende de frappe:

'A' - A

'C' - Ctrl + A

'S' - Ctrl + C

'V' - Ctrl + V


Code:

 #include  #include  #include  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 

En utilisant les astuces mentionnées dans les réponses ci-dessus, Mathématiquement, Solution peut être expliquée dans une équation comme suit:

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5]. où [] est le plus grand facteur entier

Il y a un compromis entre l’impression manuelle des mA, puis en utilisant Ctrl + A , Ctrl + C et Nm-2 Ctrl + V. La meilleure solution est au milieu. Si le nombre de touches maximum est égal à 10, la meilleure solution consiste à taper 5 A ou 4 A.

essayez d’utiliser ce look à cette http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ et optimisez peut-être un peu la recherche des résultats vers le milieu point.

Voici ma solution avec la programmation dynamic, sans boucle nestede, et qui imprime également les caractères réels que vous devez taper:

 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) ssortingng 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])) 

Ceci est la sortie (“a” signifie “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 N Strokes sont autorisés, le résultat est N-3.

A’s -> N-3

CTRL + A -> Sélection de ces N caractères: +1

CTRL + C -> Copier ces N caractères: +1

Ctrl + V -> Coller les N caractères. : +1 ie, (Puisque nous avons sélectionné les caractères entiers en utilisant CTRL + A ) Remplacer ces caractères N-3 existants par les caractères N-3 copiés (qui remplacent les mêmes caractères) et le résultat est N-3.