Maximale Anzahl von Zeichen mit den Tastenanschlägen A, Strg + A, Strg + C und Strg + V.

Dies ist eine Interviewfrage von Google. Ich kann es nicht alleine lösen. Kann jemand etwas Licht ins Dunkel bringen?

Schreiben Sie ein Programm, um die Folge von Tastenanschlägen so zu drucken, dass die maximale Anzahl von Zeichen 'A' generiert wird. Sie dürfen nur 4 Tasten verwenden : A, Ctrl+ A, Ctrl+ Cund Ctrl+ V. Es sind nur N Tastenanschläge zulässig. Alle Ctrl+ Zeichen werden als ein Tastendruck betrachtet, also ist Ctrl+ Aein Tastendruck.

Zum Beispiel kann die Sequenz A, Ctrl+ A, Ctrl+ C, Ctrl+ Verzeugt zwei A die in 4 Tastenanschlägen.

• Strg + A ist Alle auswählen
• Strg + C ist Kopieren
• Strg + V ist Einfügen

Ich habe etwas Mathematik gemacht. Für jedes N können wir mit x Zahlen von A, eins Ctrl+ A, eins Ctrl+ Cund y Ctrl+ Veine maximale ((N-1) / 2) ² Anzahl von A erzeugen . Für einige N> M ist es besser, so viele Ctrl+ A, Ctrl+ Cund Ctrl+ VSequenzen zu verwenden, wie die Anzahl der A verdoppelt.

Die Sequenz Ctrl+ A, Ctrl+ V, Ctrl+ Cüberschreibt die vorhandene Auswahl nicht. Die kopierte Auswahl wird an die ausgewählte angehängt.

Es gibt eine dynamische Programmierlösung. Wir beginnen damit zu wissen, dass 0 Schlüssel uns zu 0 A machen können. Dann durchlaufen wir ibis zu nzwei Dinge: Drücken Sie einmal A und drücken Sie Auswahl alle + Kopieren, gefolgt von Einfügezeiten j(siehe j-i-1unten; beachten Sie den Trick hier: Der Inhalt befindet sich noch in der Zwischenablage, sodass wir ihn mehrmals ohne Einfügen einfügen können jedes Mal kopieren). Wir müssen nur bis zu 4 aufeinanderfolgende Pasten berücksichtigen, da Auswählen, Kopieren, Einfügen x 5 dem Auswählen, Kopieren, Einfügen, Auswählen, Kopieren, Einfügen entspricht. Letzteres ist besser, da wir mehr in der Zwischenablage haben. Sobald wir erreicht haben n, haben wir das gewünschte Ergebnis.

Die Komplexität scheint O (N) zu sein, aber da die Zahlen exponentiell wachsen, ist sie aufgrund der Komplexität der Multiplikation der großen Zahlen tatsächlich O (N ² ). Unten finden Sie eine Python-Implementierung. Die Berechnung für N = 50.000 dauert ungefähr 0,5 Sekunden.

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]

Stellt im Code jdie Gesamtzahl der Tasten dar, die nach unserer neuen Tastenfolge gedrückt wurden. Zu idiesem Zeitpunkt haben wir bereits Tastendrücke, und zwei neue Tastendrücke werden ausgewählt und kopiert. Deshalb treffen wir Einfügezeiten j-i-2. Da Einfügen in die bestehende Sequenz von fügt dp[i] Aist, müssen wir hinzufügen , 1so dass es j-i-1. Dies erklärt das j-i-1in der vorletzten Zeile.

Hier sind einige Ergebnisse ( n=> Anzahl der A):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• 1.000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• 50.000 => eine sehr große Zahl!

Ich stimme @SB zu, dass Sie immer Ihre Annahmen angeben sollten: Meine ist, dass Sie nicht zweimal einfügen müssen, um die Anzahl der Zeichen zu verdoppeln. Dies erhält die Antwort für 7, und wenn meine Lösung nicht falsch ist, muss die Annahme richtig sein.

Falls jemand fragt , warum ich nicht Folgen der Form Überprüfung Ctrl+ A, Ctrl+ C, A, Ctrl+ V: Das Endergebnis wird immer das gleiche sein wie A, Ctrl+ A, Ctrl+ C, Ctrl+ , Vdie ich tue betrachten.

Durch die Verwendung von Marcogs Lösung habe ich ein Muster gefunden, das bei beginnt n=16. Um dies zu verdeutlichen sind hier die Tastenanschläge für n=24bis zu n=29, ich ersetzt ^ A mit S (wählen), ^ C mit C (kopieren) und ^ V mit P (Paste) zur besseren Lesbarkeit:

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

Nach einer anfänglichen 4 As ist das ideale Muster zum Auswählen, Kopieren, Einfügen, Einfügen, Einfügen und Wiederholen. Dies multipliziert die Anzahl von As mit 4 alle 5 Tastenanschläge. Wenn dieses 5-Tasten-Muster die verbleibenden Tastenanschläge nicht alleine verbrauchen kann, verbrauchen einige 4-Tasten-Muster (SCPP) die letzten Tastenanschläge und ersetzen SCPPP (oder entfernen eine der Pasten) nach Bedarf. Die 4 Tastenanschläge multiplizieren die Summe mit 3 alle 4 Tastenanschläge.

Bei Verwendung dieses Musters handelt es sich um Python-Code, der die gleichen Ergebnisse wie die Lösung von marcog erzielt, jedoch O (1) bearbeitet : Dies ist tatsächlich O (log n) aufgrund von Potenzierung, danke an IVlad für den Hinweis.

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)

Berechnung von e3: Am Ende der Tastenanschlagliste stehen immer zwischen 0 und 4 SCPP-Muster, denn n % 5 == 4es gibt 4, n % 5 == 1es gibt 3, n % 5 == 2es gibt 2, n % 5 == 3es gibt 1 und n % 5 == 4es gibt 0. Dies kann vereinfacht werden (4 - n) % 5.

Berechnung von e4: Die Gesamtzahl der Muster erhöht sich jedes Mal um 1 n % 5 == 0, wie sich herausstellt, erhöht sich diese Anzahl auf genau n / 5. Mit der Bodenteilung können wir die Gesamtzahl der Muster erhalten, die Gesamtzahl für e4ist die Gesamtzahl der Muster minus e3. Für diejenigen, die mit Python nicht vertraut sind, //ist die zukunftssichere Notation für die Bodenteilung.

So würde ich es angehen:

• annehmen CtrlA= alle auswählen
• annehmen CtrlC= Kopierauswahl
• nehmen CtrlV= kopierte Auswahl einfügen

Bei einem bestimmten Text sind 4 Tastenanschläge erforderlich, um ihn zu duplizieren:

• CtrlA um alles auszuwählen
• CtrlC um es zu kopieren
• CtrlV zum Einfügen (dies wird über die Auswahl eingefügt - STELLEN SIE IHRE ANNAHMEN AN)
• CtrlV wieder einfügen, was es verdoppelt.

Von dort aus können Sie 4 oder 5 A machen und dann die obigen Schritte durchlaufen. Beachten Sie, dass ctrl + a, c, v, vIhr Text beim Durchlaufen exponentiell wächst. Wenn die verbleibenden Striche <4 sind, machen Sie einfach weiter aCtrlV

Der Schlüssel zu Interviews an Orten wie Google besteht darin, Ihre Annahmen anzugeben und Ihr Denken zu kommunizieren. Sie wollen wissen, wie Sie Probleme lösen.

Es ist in O (1) lösbar: Wie bei den Fibonacci-Zahlen gibt es eine Formel zur Berechnung der Anzahl der gedruckten As (und der Reihenfolge der Tastenanschläge):

1) Wir können die Problembeschreibung vereinfachen:

• Nur [A], [Ca] + [Cc], [Cv] und einen leeren Copy-Paste-Puffer

gleich

• mit nur [Ca] + [Cc], [Cv] und "A" im Copy-Paste-Puffer.

2) Wir können die Folge von Tastenanschlägen als eine Folge von N Zeichen aus {'*', 'V', 'v'} beschreiben, wobei 'v' [Cv] und '*' [Ca] und 'V bedeutet 'bedeutet [Cc]. Beispiel: "vvvv * Vvvvv * Vvvv"

Die Länge dieser Zeichenfolge entspricht immer noch N.

Das Produkt der Längen der Vv-Wörter in dieser Zeichenfolge entspricht der Anzahl der produzierten As.

3) Bei einer festen Länge N für diese Zeichenfolge und einer festen Anzahl K von Wörtern ist das Ergebnis maximal, wenn alle Wörter nahezu gleich lang sind. Ihr paarweiser Unterschied beträgt nicht mehr als ± 1.

Was ist nun die optimale Zahl K, wenn N gegeben ist?

4) Angenommen, wir möchten die Anzahl der Wörter erhöhen, indem wir ein einzelnes Wort der Länge L anhängen. Dann müssen wir L + 1-mal jedes vorherige Wort um ein 'v' reduzieren. Beispiel: "... * Vvvv * Vvvv * Vvvv * Vvvv" -> "... * Vvv * Vvv * Vvv * Vvv * Vvv"

Was ist nun die optimale Wortlänge L?

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

=> Optimal ist L = 4.

5) Angenommen, wir haben ein ausreichend großes N, um eine Zeichenfolge mit vielen Wörtern der Länge 4 zu erzeugen, aber es bleiben einige Tastenanschläge übrig. Wie sollen wir sie verwenden?

• Wenn noch 5 oder mehr übrig sind: Fügen Sie ein weiteres Wort mit der Länge 4 hinzu.

• Wenn noch 0 übrig sind: Fertig.

• Wenn noch 4 übrig sind: Wir könnten es auch

  a) Fügen Sie ein Wort mit der Länge 3: 4 * 4 * 4 * 4 * 3 = 768 hinzu.

  b) oder erhöhen Sie 4 Wörter auf Länge 5: 5 * 5 * 5 * 5 = 625. => Ein Wort anzuhängen ist besser.

• Wenn noch 3 übrig sind: Wir könnten es auch

  a) oder fügen Sie ein Wort mit der Länge 3 hinzu, indem Sie das vorherige Wort von Länge 4 auf 3 einstellen: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.

  b) Erhöhen Sie 3 Wörter auf Länge 5: 5 * 5 * 5 = 125. => Ein Wort anzuhängen ist besser.

• Wenn noch 2 übrig sind: Wir könnten es auch

  a) oder fügen Sie ein Wort mit der Länge 3 hinzu, indem Sie die vorherigen zwei Wörter von der Länge 4 auf 3 einstellen: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.

  b) Erhöhen Sie 2 Wörter auf Länge 5: 5 * 5 = 25. => Ein Wort anzuhängen ist besser.

• Wenn noch 1 übrig ist: Wir könnten es auch

  a) oder fügen Sie ein Wort mit der Länge 3 hinzu, indem Sie die vorherigen drei Wörter von Länge 4 auf 3 einstellen: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.

  b) Erhöhen Sie ein Wort auf Länge 5: 4 * 4 * 5 = 80. => Ein Wort anzuhängen ist besser.

6) Was ist nun, wenn wir kein "ausreichend großes N" haben, um die Regeln in 5) zu verwenden? Wir müssen uns an Plan b) halten, wenn möglich! Die Zeichenfolgen für kleines N sind:

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) Was ist nun die optimale Anzahl K von Wörtern in einer Zeichenfolge der Länge N?

Wenn N <7, dann ist K = 1, sonst wenn 6 <N <11, dann ist K = 2; sonst: K = Ceil ((N + 1) / 5)

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

Und wenn N> 10 ist, ist die Anzahl der Wörter mit der Länge 3: K * 5-1-N. Damit können wir die Anzahl der gedruckten As berechnen:

Wenn N> 10 ist, ist die Anzahl von As: 4 ^ {N + 1-4K} · 3 ^ {5K-N-1}

Die Verwendung von CtrlA+ CtrlC+ CtrlVist erst nach 4 'A von Vorteil.

Also würde ich so etwas machen (im Pseudo-BASIC-Code, da Sie keine richtige Sprache angegeben haben):

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

Bearbeiten

1. Zurück zur Verwendung einer Single CtrlVin der Hauptschleife.
2. Es wurden einige Kommentare hinzugefügt, um zu erklären, was ich hier versuche.
3. Es wurde ein Problem mit dem Block "Die ersten vier A" behoben.

Es sind 3 Tastenanschläge erforderlich, um die Anzahl der As zu verdoppeln. Es ist nur sinnvoll, mit dem Verdoppeln zu beginnen, wenn Sie 3 oder mehr wie bereits gedruckt haben. Sie möchten, dass Ihr letzter zulässiger Tastenanschlag ein ist CtrlV, um sicherzustellen, dass Sie die größtmögliche Zahl verdoppeln. Um ihn auszurichten, füllen wir nach den ersten drei As am Anfang alle zusätzlichen Tastenanschläge mit mehr As aus.

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");
}

Bearbeiten:

Das ist schrecklich, ich habe mich selbst völlig übertroffen und nicht mehrere Pasten für jede Kopie in Betracht gezogen.

Bearbeiten 2:

Ich glaube, 3-maliges Einfügen ist optimal, wenn Sie genug Tastenanschläge haben, um dies zu tun. In 5 Tastenanschlägen multiplizieren Sie Ihre Anzahl von As mit 4. Dies ist besser als das Multiplizieren mit 3 mit 4 Tastenanschlägen und besser als das Multiplizieren mit 5 mit 6 Tastenanschlägen. Ich verglich dies, indem ich jeder Methode die gleiche Anzahl von Tastenanschlägen gab, so dass jeder zur gleichen Zeit einen Zyklus beendete (60), wobei der 3-Multiplikator 15 Zyklen, der 4-Multiplikator 12 Zyklen und der 5-Multiplikator ausführen ließ. Multiplikator machen 10 Zyklen. 3 ^ 15 = 14.348.907, 4 ^ 12 = 16.777.216 und 5 ^ 10 = 9.765.625. Wenn nur noch 4 Tastenanschläge übrig sind, ist es besser, einen 3-Multiplikator auszuführen, als 4 weitere Male einzufügen, wodurch der vorherige 4-Multiplikator im Wesentlichen zu einem 8-Multiplikator wird. Wenn nur noch 3 Tastenanschläge übrig sind, ist ein 2-Multiplikator am besten.

Angenommen, Sie haben x Zeichen in der Zwischenablage und x Zeichen im Textbereich. Nennen wir es "Zustand x".

Drücken wir ein paar Mal auf "Einfügen" (ich bezeichne es der Einfachheit m-1halber mit), dann auf "Alles auswählen" und "Kopieren". Nach dieser Sequenz gelangen wir zum "Zustand m * x". Hier haben wir insgesamt m + 1 Tastenanschläge verschwendet. Das asymptotische Wachstum ist also (zumindest) so etwas wie f^nf = m^(1/(m+1)). Ich glaube, es ist das maximal mögliche asymptotische Wachstum, obwohl ich es (noch) nicht beweisen kann.

Das Ausprobieren verschiedener Werte von m zeigt, dass das Maximum für f für erhalten wird m=4.

Verwenden wir den folgenden Algorithmus:

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

(nicht sicher, ob es das optimale ist).

Die Häufigkeit, mit der A zu Beginn gedrückt wird, beträgt 3: Wenn Sie 4 Mal drücken, verpassen Sie die Gelegenheit, die Anzahl der A in 3 weiteren Tastenanschlägen zu verdoppeln.

Das Drücken von Einfügen am Ende beträgt höchstens 5: Wenn Sie noch 6 oder mehr Tastenanschläge haben, können Sie stattdessen Einfügen, Einfügen, Einfügen, Alles auswählen, Kopieren, Einfügen verwenden.

Wir erhalten also den folgenden Algorithmus:

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

(nicht sicher, ob es das optimale ist). Die Anzahl der Zeichen nach der Ausführung ist ungefähr so

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

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

Im Folgenden wird die zweite Bearbeitung des OP verwendet, bei der das Einfügen vorhandenen Text nicht ersetzt.

Beachten Sie einige Dinge:

• ^ A und ^ C können als eine einzelne Aktion betrachtet werden, die zwei Tastenanschläge erfordert, da es niemals sinnvoll ist, sie einzeln auszuführen. Tatsächlich können wir alle Instanzen von ^ A ^ C durch ^ K ^ V ersetzen, wobei ^ K eine Ein-Schlüssel- Schnittoperation ist (lassen Sie es uns X abkürzen). Wir werden sehen, dass der Umgang mit ^ K viel schöner ist als der Zwei-Kosten-^ A ^ C.
• Nehmen wir an, dass ein 'A' in der Zwischenablage beginnt. Dann ist ^ V (lassen Sie es uns mit Y abkürzen) A streng überlegen, und wir können letzteres aus allen Überlegungen herausnehmen. (Wenn die Zwischenablage im eigentlichen Problem leer ist, ersetzen wir im Folgenden nur Y durch A anstelle von ^ V bis zum ersten X.)

Jede vernünftige Tastenfolge kann somit als eine durch X getrennte Gruppe von Ys interpretiert werden, beispielsweise YYYXYXYYXY. Bezeichne mit V (s) die Anzahl von 'A', die durch die Sequenz s erzeugt werden. Dann ist V (nXm) = V (n) * V (m), weil X im Wesentlichen jedes Y in m durch V (n) 'A ersetzt.

Das Copy-Paste-Problem ist daher isomorph zu dem folgenden Problem: "Verwenden von m + 1-Zahlen, die sich zu Nm summieren, maximieren Sie ihr Produkt." Wenn beispielsweise N = 6 ist, lautet die Antwort m = 1 und die Zahlen (2,3). 6 = 2 · 3 = V (JJJJJ) = V (AA ^ A ^ C ^ V ^ V) (oder V (JJJXJJ) = V (AAA ^ A ^ C ^ V).)

Wir können einige Beobachtungen machen:

Für einen festen Wert von msind die zu wählenden Zahlen ceil( (N-m)/(m+1) )und floor( (N-m)/(m+1) )(in welcher Kombination auch immer die Summe funktioniert; genauer gesagt, Sie benötigen (N-m) % (m+1) ceilsund die restlichen floors). Dies liegt daran, dass z a < b.(a+1)*(b-1) >= a*b .

Leider sehe ich keinen einfachen Weg, um den Wert von zu finden m. Wenn dies mein Interview wäre, würde ich an dieser Stelle zwei Lösungen vorschlagen:

Option 1. Alle möglichen Schleifen durchlaufen m. Eine O ( n log n) -Lösung.

C ++ - Code:

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

Option 2. Erlauben Sie m, nicht ganzzahlige Werte zu erreichen und den optimalen Wert zu finden, indem Sie die Ableitung von [(N-m)/(m+1)]^min Bezug auf mdie Wurzel nehmen und nach dieser suchen . Es gibt keine analytische Lösung, aber die Wurzel kann beispielsweise mit der Newtonschen Methode gefunden werden. Verwenden Sie dann den Boden und die Decke dieser Wurzel für den Wert von mund wählen Sie die beste aus.

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

Hier ist mein Ansatz und meine Lösung mit dem folgenden Code.

Ansatz:

Es gibt drei verschiedene Operationen, die ausgeführt werden können.

1. Tastenanschlag A - Gibt ein Zeichen 'A' aus.
2. Tastenanschlag (Strg-A) + (Strg-C) - Gibt im Wesentlichen nichts aus. Diese beiden Tastenanschläge können zu einer Operation kombiniert werden, da jeder dieser Tastenanschläge für sich genommen keinen Sinn ergibt. Dieser Tastendruck richtet auch die Ausgabe für den nächsten Einfügevorgang ein.
3. Tastenanschlag (Strg-V) - Die Ausgabe für diesen Tastenanschlag hängt wirklich von der vorherigen (zweiten) Operation ab, und daher müssten wir dies in unserem Code berücksichtigen.

Angesichts der drei unterschiedlichen Operationen und ihrer jeweiligen Ausgaben müssen wir nun alle Permutationen dieser Operationen durchlaufen.

Annahme:

In einer Version dieses Problems heißt es nun, dass die Tastenfolge Strg + A -> Strg + C -> Strg + V die hervorgehobene Auswahl überschreibt. Um diese Annahme zu berücksichtigen, muss der folgenden Lösung nur eine Codezeile hinzugefügt werden, in der die gedruckte Variable in Fall 2 auf 0 gesetzt ist

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

Für diese Lösung

Der folgende Code gibt einige Sequenzen aus und die letzte Sequenz ist die richtige Antwort für jedes gegebene N. ZB für N = 11 ist dies die richtige Sequenz

Mit der Annahme

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

Ohne die Annahme

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

Ich habe beschlossen, die Annahme für diese Lösung beizubehalten.

Tastenanschlag-Legende:

'A' - A.

'C' - Strg + A.

'S' - Strg + C.

'V' - Strg + V.

Code:

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

Unter Verwendung der in den obigen Antworten genannten Tricks kann die Lösung mathematisch in einer Gleichung wie folgt erklärt werden:

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5]. Dabei ist [] der größte ganzzahlige Faktor

Es gibt einen Kompromiss zwischen dem manuellen Drucken von mA und der Verwendung von Ctrl+ A, Ctrl+ Cund Nm-2 Ctrl+ V. Die beste Lösung ist in der Mitte. Wenn max. Tastenanschläge = 10 sind, ist die beste Lösung die Eingabe von 5 A oder 4 A.

Versuchen Sie es mit diesem Look. Schauen Sie sich diesen http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ an und optimieren Sie möglicherweise ein wenig, um nach den Ergebnissen in der Mitte zu suchen Punkt.

Hier ist meine Lösung mit dynamischer Programmierung ohne verschachtelte Schleife, die auch die tatsächlichen Zeichen druckt, die Sie eingeben müssen:

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

Dies ist die Ausgabe ('a' bedeutet 'STRG + A' usw.)

 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 

Wenn N Tastenanschläge zulässig sind, ist das Ergebnis N-3.

A's -> N-3

CTRL+ A-> Auswahl dieser N Zeichen: +1

CTRL+ C-> Kopieren dieser N Zeichen: +1

Ctrl+ V-> Einfügen der N Zeichen. : +1 dh (Da wir die gesamten Zeichen mit CTRL+ ausgewählt haben A) Ersetzen dieser vorhandenen N-3-Zeichen durch die kopierten N-3-Zeichen (die dieselben Zeichen überschreiben) und das Ergebnis ist N-3.