Maksymalna liczba znaków przy użyciu klawiszy A, Ctrl + A, Ctrl + C i Ctrl + V

To jest pytanie do wywiadu z Google. Nie jestem w stanie sam tego rozwiązać. Czy ktoś może rzucić trochę światła?

Napisz program, który wydrukuje sekwencję naciśnięć klawiszy tak, aby generował maksymalną liczbę znaków „A”. Masz prawo do korzystania tylko 4 przyciski: A, Ctrl+ A, Ctrl+ Ci Ctrl+ V. Dozwolonych jest tylko N naciśnięć klawiszy. Wszystkie Ctrlznaki + są traktowane jako jedno naciśnięcie klawisza, więc Ctrl+ Ato jedno naciśnięcie klawisza.

Na przykład sekwencja A, Ctrl+ A, Ctrl+ C, Ctrl+ Vtworzy dwie jest w 4 klawiszy.

• Ctrl + A to Zaznacz wszystko
• Ctrl + C to kopia
• Ctrl + V to Wklej

Zrobiłem trochę matematyki. Dla dowolnego N, używając x liczb A, jeden Ctrl+ A, jeden Ctrl+ Ci y Ctrl+ V, możemy wygenerować max ((N-1) / 2) ² liczby A. Od pewnego N> M, lepiej jest użyć tylu Ctrl+ A„s, Ctrl+ Ci Ctrl+ Vsekwencje jak to podwaja liczbę jest.

Sekwencja Ctrl+ A, Ctrl+ V, Ctrl+ Cnie nadpisze istniejącego zaznaczenia. Doda skopiowane zaznaczenie do zaznaczonego.

Istnieje dynamiczne rozwiązanie do programowania. Zaczynamy, wiedząc, że 0 kluczy może dać nam 0 szóstek. Następnie iterujemy iaż do n, wykonując dwie rzeczy: naciskając raz A i naciskając zaznacz wszystko + kopiuj, a następnie jczasy wklejania (właściwie j-i-1poniżej; zwróć uwagę na tę sztuczkę: zawartość nadal znajduje się w schowku, więc możemy wkleić ją wiele razy bez kopiowanie za każdym razem). Musimy wziąć pod uwagę tylko 4 kolejne wklejanie, ponieważ zaznacz, kopiuj, wklej x 5 jest równoważne zaznaczaniu, kopiowaniu, wklejaniu, zaznaczaniu, kopiowaniu, wklejaniu, a to drugie jest lepsze, ponieważ pozostawia nam więcej w schowku. Kiedy już osiągnęliśmy n, mamy pożądany rezultat.

Złożoność może wydawać się O (N), ale ponieważ liczby rosną w tempie wykładniczym, w rzeczywistości jest to O (N ² ) ze względu na złożoność mnożenia dużych liczb. Poniżej znajduje się implementacja Pythona. Obliczenie dla N = 50 000 zajmuje około 0,5 sekundy.

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]

W kodzie jreprezentuje całkowitą liczbę klawiszy naciśniętych po naszej nowej sekwencji naciśnięć klawiszy. iNa tym etapie mamy już naciśnięcia klawiszy, a 2 nowe naciśnięcia klawiszy służą do wybierania wszystkiego i kopiowania. Dlatego osiągamy j-i-2czasy wklejania . Ponieważ wklejanie dodaje do istniejącej sekwencji dp[i] A, musimy dodać 1ją tworząc j-i-1. To wyjaśnia j-i-1w przedostatnim wierszu.

Oto kilka wyników ( n=> liczba liter A):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• 1,000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• 50 000 => bardzo duża liczba!

Zgadzam się z @SB, że zawsze powinieneś podawać swoje założenia: Moje jest takie, że nie musisz wklejać dwa razy, aby podwoić liczbę znaków. To daje odpowiedź na 7, więc jeśli moje rozwiązanie jest błędne, założenie musi być poprawne.

W przypadku gdy ktoś zastanawia się, dlaczego nie jestem sprawdzanie sekwencji postaci Ctrl+ A, Ctrl+ C, A, Ctrl+ V: Wynik końcowy będzie zawsze taka sama jak A, Ctrl+ A, Ctrl+ C, Ctrl+ Vktóre należy rozważyć.

Korzystając z rozwiązania marcog, znalazłem wzór, który zaczyna się od n=16. Aby to zilustrować, oto skróty klawiszowe n=24do n=29, zamieniłem ^ A na S (wybierz), ^ C na C (kopiowanie) i ^ V na P (wklej) dla czytelności:

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

Po początkowych 4 As, idealnym wzorcem jest zaznaczanie, kopiowanie, wklejanie, wklejanie, wklejanie i powtarzanie. Spowoduje to pomnożenie liczby As przez 4 co 5 naciśnięć klawiszy. Jeśli ten wzór 5 naciśnięć klawiszy nie może samodzielnie zużywać pozostałych naciśnięć klawiszy, pewna liczba 4 wzorców naciśnięć klawiszy (SCPP) zużywa ostatnie naciśnięcia klawiszy, zastępując SCPPP (lub usuwając jedną z past) w razie potrzeby. 4 wzorce naciśnięć klawiszy mnożą sumę przez 3 co 4 naciśnięcia.

Używając tego wzorca tutaj, jest kod Pythona, który daje takie same wyniki jak rozwiązanie marcog, ale jest to edycja O (1) : To jest w rzeczywistości O (log n) z powodu potęgowania, dzięki IVladowi za wskazanie tego.

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)

Obliczanie e3: Na końcu listy naciśnięć klawiszy zawsze znajduje się od 0 do 4 wzorców SCPP, ponieważ n % 5 == 4są 4, n % 5 == 1są 3, n % 5 == 2są 2, n % 5 == 3jest 1 i n % 5 == 4jest 0. Można to uprościć do (4 - n) % 5.

Obliczanie e4: Całkowita liczba wzorów wzrasta o 1 za każdym razem n % 5 == 0, gdy okazuje się, że liczba ta rośnie dokładnie n / 5. Korzystając z podziału piętra, możemy uzyskać całkowitą liczbę wzorów, łączna liczba e4to całkowita liczba wzorów minus e3. Dla osób niezaznajomionych z Pythonem //jest to przyszłościowa notacja podziału pięter.

Oto, jak bym do tego podejść:

• zakładaj CtrlA= wybierz wszystko
• zakładać CtrlC= kopiuj zaznaczenie
• zakładaj CtrlV= wklej skopiowany wybór

biorąc pod uwagę tekst, do jego skopiowania potrzeba 4 naciśnięć klawiszy:

• CtrlA aby wybrać wszystko
• CtrlC skopiować
• CtrlV do wklejenia (spowoduje to wklejenie zaznaczenia - PODAJ SWOJE ZAŁOŻENIA)
• CtrlV wkleić ponownie, co podwaja go.

Stamtąd możesz rozważyć zrobienie 4 lub 5 A, a następnie powtórzenie powyższego. Pamiętaj, że działanie ctrl + a, c, v, vspowoduje wykładniczy wzrost tekstu w trakcie przeglądania. Jeśli pozostałe pociągnięcia są <4, po prostu rób dalejCtrlV

Kluczem do wywiadów w miejscach takich jak Google jest przedstawienie swoich założeń i przekazanie swoich przemyśleń. chcą wiedzieć, jak rozwiązujesz problemy.

Można to rozwiązać w O (1): Podobnie jak w przypadku liczb Fibonacciego, istnieje wzór do obliczenia liczby wydrukowanych As (i sekwencji naciśnięć klawiszy):

1) Możemy uprościć opis problemu:

• Mając tylko [A], [Ca] + [Cc], [Cv] i pusty bufor kopiuj-wklej

równa się

• mając tylko [Ca] + [Cc], [Cv] i „A” w buforze kopiuj-wklej.

2) Możemy opisać sekwencję naciśnięć klawiszy jako ciąg N znaków z {'*', 'V', 'v'}, gdzie 'v' oznacza [Cv], a '*' oznacza [Ca] i 'V „oznacza [DW]. Przykład: „vvvv * Vvvvv * Vvvv”

Długość tego sznurka nadal jest równa N.

Iloczyn długości słów Vv w tym ciągu jest równy liczbie wyprodukowanych As.

3) Biorąc pod uwagę stałą długość N dla tego ciągu i stałą liczbę K słów, wynikiem będzie maksymalna, jeśli wszystkie słowa mają prawie taką samą długość. Ich różnica w parach nie przekracza ± 1.

Jaka jest optymalna liczba K, jeśli podano N?

4) Załóżmy, że chcemy zwiększyć liczbę słów, dodając jedno słowo o długości L, a następnie musimy zmniejszyć L + 1 razy dowolne poprzednie słowo o jedno „v”. Przykład: „… * Vvvv * Vvvv * Vvvv * Vvvv” -> „… * Vvv * Vvv * Vvv * Vvv * Vvv”

Jaka jest optymalna długość słowa L?

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

=> Optymalne jest L = 4.

5) Załóżmy, że mamy wystarczająco duże N, aby wygenerować łańcuch z wieloma słowami o długości 4, ale zostało kilka naciśnięć klawiszy; jak powinniśmy ich używać?

• Jeśli pozostało 5 lub więcej: Dodaj kolejne słowo o długości 4.

• Jeśli pozostało 0: Gotowe.

• Jeśli pozostały 4: możemy też

  a) dołącz jedno słowo o długości 3: 4 * 4 * 4 * 4 * 3 = 768.

  b) lub zwiększ 4 słowa do długości 5: 5 * 5 * 5 * 5 = 625. => Lepiej jest dołączyć jedno słowo.

• Jeśli pozostały 3: możemy też

  a) lub dołącz jedno słowo o długości 3, dostosowując poprzednie słowo od długości 4 do 3: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.

  b) zwiększ 3 słowa do długości 5: 5 * 5 * 5 = 125. => Lepiej jest dołączyć jedno słowo.

• Jeśli pozostały 2: możemy też

  a) lub dołącz jedno słowo o długości 3, dostosowując poprzednie dwa słowa od długości 4 do 3: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.

  b) zwiększ 2 słowa do długości 5: 5 * 5 = 25. => Lepiej jest dołączyć jedno słowo.

• Jeśli zostanie 1: możemy też

  a) lub dołącz jedno słowo o długości 3, dostosowując poprzednie trzy słowa od długości 4 do 3: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.

  b) dodać jedno słowo do długości 5: 4 * 4 * 5 = 80. => Lepiej jest dołączyć jedno słowo.

6) A co, jeśli nie mamy „wystarczająco dużego N”, aby zastosować reguły z 5)? Musimy trzymać się planu b), jeśli to możliwe! Ciągi dla małego N to:

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) Jaka jest optymalna liczba K słów w ciągu o długości N?

Jeśli N <7, to K = 1, w przeciwnym razie 6 <N <11, to K = 2; w przeciwnym razie: K = ceil ((N + 1) / 5)

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

A jeśli N> 10, to liczba słów o długości 3 wyniesie: K * 5-1-N. Dzięki temu możemy obliczyć liczbę wydrukowanych As:

Jeśli N> 10, liczba As będzie: 4 ^ {N + 1-4K} · 3 ^ {5K-N-1}

Używanie CtrlA+ CtrlC+ CtrlVjest zaletą dopiero po 4 'szóstkach.

Więc zrobiłbym coś takiego (w pseudo-BASIC-kodzie, ponieważ nie określiłeś żadnego właściwego języka):

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

Edytować

1. Wróćmy do używania singla CtrlVw głównej pętli.
2. Dodano kilka komentarzy, aby wyjaśnić, co próbuję tutaj zrobić.
3. Naprawiono problem z blokiem „pierwsze cztery szóstki”.

Potrzeba 3 naciśnięć klawiszy, aby podwoić liczbę As. Podwajanie ma sens tylko wtedy, gdy masz 3 lub więcej Jak już wydrukowano. Chcesz, aby ostatnie dozwolone naciśnięcie klawisza było a, CtrlVaby upewnić się, że podwajasz największą liczbę, jaką możesz, więc aby ją wyrównać, wypełnimy wszelkie dodatkowe naciśnięcia klawiszy po pierwszych trzech Jak na początku z większą liczbą 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");
}

Edytować:

To okropne, całkowicie wyprzedziłem siebie i nie rozważałem wielu past dla każdej kopii.

Edycja 2:

Uważam, że wklejanie 3 razy jest optymalne, gdy masz wystarczająco dużo klawiszy, aby to zrobić. W 5 naciśnięciach klawiszy pomnóż liczbę As przez 4. Jest to lepsze niż mnożenie przez 3 za pomocą 4 naciśnięć klawiszy i lepsze niż mnożenie przez 5 za pomocą 6 naciśnięć klawiszy. Porównałem to, dając każdej metodzie taką samą liczbę naciśnięć klawiszy, na tyle, aby każdy z nich zakończył cykl w tym samym czasie (60), pozwalając mnożnikowi 3 na 15 cykli, mnożnikowi 4 na 12 cykli, a 5 mnożnik do 10 cykli. 3 ^ 15 = 14 348 907, 4 ^ 12 = 16 777 216 i 5 ^ 10 = 9 765 625. Jeśli pozostały tylko 4 naciśnięcia klawiszy, wykonanie mnożenia 3 jest lepsze niż wklejanie 4 razy więcej, zasadniczo sprawiając, że poprzednie 4 mnożniki stają się mnożnikiem 8. Jeśli pozostały tylko 3 naciśnięcia klawiszy, najlepszy jest mnożnik 2.

Załóżmy, że masz x znaków w schowku i x znaków w obszarze tekstowym; nazwijmy to „stanem x”.

Naciśnijmy kilka razy „Wklej” ( m-1dla wygody oznaczam to przez ), a następnie „Zaznacz wszystko” i „Kopiuj”; po tej sekwencji dochodzimy do „stanu m * x”. Tutaj zmarnowaliśmy łącznie m + 1 naciśnięć klawiszy. Zatem asymptotyczny wzrost jest (przynajmniej) podobny do tego f^n, gdzie f = m^(1/(m+1)). Uważam, że jest to maksymalny możliwy asymptotyczny wzrost, chociaż nie mogę tego udowodnić (jeszcze).

Wypróbowanie różnych wartości m pokazuje, że maksimum dla f uzyskuje się dla m=4.

Skorzystajmy z następującego algorytmu:

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

(nie jestem pewien, czy jest optymalny).

Liczba naciśnięć A na początku wynosi 3: jeśli naciśniesz go 4 razy, stracisz możliwość podwojenia liczby A w 3 kolejnych naciśnięciach klawiszy.

Liczba naciśnięć Wklej na końcu nie przekracza 5: jeśli pozostało 6 lub więcej naciśnięć klawiszy, możesz zamiast tego użyć Wklej, Wklej, Wklej, Zaznacz wszystko, Kopiuj, Wklej.

Otrzymujemy więc następujący algorytm:

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

(nie jestem pewien, czy jest optymalny). Liczba znaków po wykonaniu tego jest podobna

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

Przykładowe wartości: 1,2,3,4,5,6,9,12,15,18,24,36,48,60,72,96,144,192,240,288, ...

Poniższy tekst wykorzystuje drugą edycję OP, która polega na tym, że wklejanie nie zastępuje istniejącego tekstu.

Zwróć uwagę na kilka rzeczy:

• ^ A i ^ C można uznać za pojedyncze działanie, które wymaga dwóch naciśnięć klawiszy, ponieważ wykonywanie ich indywidualnie nigdy nie ma sensu. W rzeczywistości możemy zamienić wszystkie wystąpienia ^ A ^ C na ^ K ^ V, gdzie ^ K jest operacją "wycinania" z jednym klawiszem (skróćmy to X). Zobaczymy, że radzenie sobie z ^ K jest znacznie przyjemniejsze niż z dwoma kosztami ^ A ^ C.
• Załóżmy, że w schowku zaczyna się litera „A”. Wtedy ^ V (skróćmy to Y) jest ściśle lepsze od A i możemy odrzucić to drugie ze wszystkich rozważań. (W rzeczywistym problemie, jeśli schowek zacznie się pusty, w dalszej części po prostu zamienimy Y na A zamiast ^ V aż do pierwszego X.)

Każda rozsądna sekwencja naciśnięć klawiszy może być zatem zinterpretowana jako grupa Y oddzielonych znakami X, na przykład YYYXYXYYXY. Oznaczmy przez V (s) liczbę 'A wyprodukowanych przez ciąg s. Wtedy V (nXm) = V (n) * V (m), ponieważ X zasadniczo zastępuje każde Y w m przez V (n) 'A.

Problem kopiuj-wklej jest zatem izomorficzny z następującym problemem: „używając liczb m + 1, które sumują się do Nm, maksymalizuj ich iloczyn”. Na przykład, gdy N = 6, odpowiedź brzmi m = 1, a liczby (2,3). 6 = 2 * 3 = V (YYXYYY) = V (AA ^ A ^ C ^ V ^ V) (lub V (YYYXYY) = V (AAA ^ A ^ C ^ V).)

Możemy poczynić kilka obserwacji:

W przypadku ustalonej wartości mliczb do wyboru są ceil( (N-m)/(m+1) )i floor( (N-m)/(m+1) )(w dowolnej kombinacji, która sprawi, że suma się sprawdzi, a dokładniej będziesz potrzebować (N-m) % (m+1) ceilsi reszty floor). Dzieje się tak dlatego, gdyż a < b, (a+1)*(b-1) >= a*b.

Niestety nie widzę łatwego sposobu na znalezienie wartości m. Gdyby to był mój wywiad, zaproponowałbym w tym miejscu dwa rozwiązania:

Opcja 1. Pętla nad wszystkimi możliwymi m. n log nRozwiązanie O ( ).

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

Opcja 2. Pozwól muzyskać wartości niecałkowite i znajdź jej optymalną wartość, biorąc pochodną funkcji [(N-m)/(m+1)]^mwzględem mi rozwiązując jej pierwiastek. Nie ma rozwiązania analitycznego, ale korzeń można znaleźć np. Metodą Newtona. Następnie użyj podłogi i sufitu tego pierwiastka jako wartości mi wybierz najlepszą z nich.

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

Oto moje podejście i rozwiązanie z kodem poniżej.

Podejście:

Można wykonać trzy różne operacje.

1. Keystroke A - generuje jeden znak `` A ''
2. Keystroke (Ctrl-A) + (Ctrl-C) - zasadniczo nic nie wyświetla. Te dwa naciśnięcia klawiszy można połączyć w jedną operację, ponieważ każde z nich z osobna nie ma sensu. Również to naciśnięcie klawisza ustawia dane wyjściowe dla następnej operacji wklejania.
3. Keystroke (Ctrl-V) - Wynik dla tego naciśnięcia klawisza naprawdę zależy od poprzedniej (drugiej) operacji i dlatego musielibyśmy to uwzględnić w naszym kodzie.

Teraz, biorąc pod uwagę trzy różne operacje i ich odpowiednie wyniki, musimy przejść przez wszystkie permutacje tych operacji.

Założenie:

Teraz w niektórych wersjach tego problemu stwierdza się, że sekwencja naciśnięć klawiszy, Ctrl + A -> Ctrl + C -> Ctrl + V, nadpisuje podświetlony wybór. Aby uwzględnić to założenie, wystarczy dodać tylko jedną linię kodu do poniższego rozwiązania, w którym drukowana zmienna w przypadku 2 jest ustawiona na 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;    
            }

Do tego rozwiązania

Poniższy kod wypisze kilka sekwencji, a ostatnia sekwencja jest poprawną odpowiedzią dla dowolnego podanego N. np. Dla N = 11 będzie to poprawna sekwencja

Z założeniem

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

Bez założenia

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

Postanowiłem zachować założenie dla tego rozwiązania.

Legenda klawiszy:

„A” - A

„C” - Ctrl + A

„S” - Ctrl + C

„V” - Ctrl + V

Kod:

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

Korzystając ze sztuczek wymienionych w odpowiedziach powyżej, Matematycznie rozwiązanie można wyjaśnić w jednym równaniu jako,

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5]. gdzie [] jest największym współczynnikiem całkowitym

Istnieje kompromis między ręcznym drukowaniem mA, a następnie użyciem Ctrl+ A, Ctrl+ Ci Nm-2 Ctrl+ V. Najlepsze rozwiązanie znajduje się pośrodku. Jeśli maksymalna liczba naciśnięć klawiszy = 10, najlepszym rozwiązaniem jest wpisanie 5 lub 4 liter.

spróbuj użyć tego Spójrz na http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ i może trochę zoptymalizuj, szukając wyników mniej więcej w połowie punkt.

Oto moje rozwiązanie z programowaniem dynamicznym, bez zagnieżdżonej pętli, które również drukuje rzeczywiste znaki, które trzeba wpisać:

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

To jest wynik („a” oznacza „CTRL + A” itp.)

 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 

Jeśli dozwolonych jest N uderzeń klawisza, wynikiem jest N-3.

A's -> N-3

CTRL+ A-> Wybieranie tych znaków N: +1

CTRL+ C-> Kopiowanie tych znaków N: +1

Ctrl+ V-> Wklejanie znaków N. : +1 tj. (Ponieważ wybraliśmy całe znaki za pomocą CTRL+ A) Zastąpienie tych istniejących N-3 znaków skopiowanymi N-3 Znakami (które zastępują te same znaki) i wynikiem jest N-3.