Jumlah karakter maksimum menggunakan penekanan tombol A, Ctrl + A, Ctrl + C dan Ctrl + V

Ini adalah pertanyaan wawancara dari google. Saya tidak bisa menyelesaikannya sendiri. Adakah yang bisa menjelaskan?

Tulis program untuk mencetak urutan penekanan tombol sedemikian rupa sehingga menghasilkan jumlah maksimum karakter 'A'. Anda diperbolehkan untuk menggunakan hanya 4 tombol: A, Ctrl+ A, Ctrl+ Cdan Ctrl+ V. Hanya diperbolehkan menekan tombol N. Semua Ctrl+ karakter dianggap sebagai satu tombol, jadi Ctrl+ Aadalah satu tombol.

Misalnya, urutan A, Ctrl+ A, Ctrl+ C, Ctrl+ Vmenghasilkan dua A dalam 4 penekanan tombol.

• Ctrl + A adalah Pilih Semua
• Ctrl + C adalah Salin
• Ctrl + V adalah Tempel

Saya melakukan matematika. Untuk setiap N, menggunakan x bilangan A, satu Ctrl+ A, satu Ctrl+ Cdan y Ctrl+ V, kita dapat menghasilkan max ((N-1) / 2) ² bilangan A. Untuk beberapa N> M, lebih baik untuk digunakan sebagai banyak Ctrl+ A's, Ctrl+ Cdan Ctrl+ Vurutan seperti menggandakan jumlah A.

Urutan Ctrl+ A, Ctrl+ V, Ctrl+ Ctidak akan menimpa pilihan yang ada. Ini akan menambahkan pilihan yang disalin ke yang dipilih.

Ada solusi pemrograman dinamis. Kita mulai dengan mengetahui bahwa 0 kunci dapat membuat kita menjadi 0 A. Kemudian kami mengulang ihingga n, melakukan dua hal: menekan A sekali dan menekan pilih semua + salin diikuti dengan jwaktu tempel (sebenarnya di j-i-1bawah; perhatikan triknya di sini: konten masih di clipboard, jadi kami dapat menempelkannya beberapa kali tanpa menyalin setiap kali). Kita hanya perlu mempertimbangkan hingga 4 paste berturut-turut, karena pilih, salin, tempel x 5 sama dengan memilih, menyalin, menempel, memilih, menyalin, menempel dan yang terakhir lebih baik karena meninggalkan kita lebih banyak di clipboard. Setelah kami mencapain , kami mendapatkan hasil yang diinginkan.

Kompleksitasnya mungkin tampak seperti O (N), tetapi karena bilangan tersebut tumbuh pada tingkat eksponensial, sebenarnya ia adalah O (N ² ) karena kerumitan mengalikan bilangan besar. Di bawah ini adalah implementasi Python. Diperlukan waktu sekitar 0,5 detik untuk menghitung 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]

Di dalam kode, jmewakili jumlah total tombol yang ditekan setelah urutan penekanan tombol baru kami. Kami sudah memiliki ipenekanan tombol pada tahap ini, dan 2 penekanan tombol baru menuju ke pilih-semua dan salin. Oleh karena itu kami menekan j-i-2waktu tempel . Karena menempelkan menambah urutan yang ada dp[i] A, kita perlu menambahkan 1membuatnya j-i-1. Ini menjelaskanj-i-1 di baris ke-2 terakhir.

Berikut adalah beberapa hasil ( n=> jumlah A):

• 7 => 9
• 8 => 12
• 9 => 16
• 10 => 20
• 100 => 1391569403904
• 1.000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304
• 50.000 => jumlah yang sangat besar!

Saya setuju dengan @SB bahwa Anda harus selalu menyatakan asumsi Anda: Milik saya adalah Anda tidak perlu menempelkan dua kali untuk menggandakan jumlah karakter. Ini mendapat jawaban untuk 7, jadi kecuali solusi saya salah, asumsi itu pasti benar.

Dalam kasus seseorang keajaiban mengapa saya tidak memeriksa urutan bentuk Ctrl+ A, Ctrl+ C, A, Ctrl+ V: Hasil akhir akan selalu sama dengan A, Ctrl+ A, Ctrl+ C, Ctrl+ Vyang saya lakukan mempertimbangkan.

Dengan menggunakan solusi marcog saya menemukan pola yang dimulai pada n=16. Untuk mengilustrasikan ini, berikut adalah penekanan tombol n=24hingga n=29, saya mengganti ^ A dengan S (pilih), ^ C dengan C (salin), dan ^ V dengan P (tempel) agar terbaca:

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

Setelah 4 As awal, pola yang ideal adalah memilih, menyalin, menempel, menempel, menempel, dan mengulang. Ini akan mengalikan jumlah As dengan 4 setiap 5 penekanan tombol. Jika pola 5 penekanan tombol ini tidak dapat menggunakan penekanan tombol yang tersisa dengan sendirinya, beberapa pola 4 penekanan tombol (SCPP) mengkonsumsi penekanan tombol terakhir, menggantikan SCPPP (atau menghapus salah satu pasta) sebagaimana diperlukan. 4 pola penekanan tombol mengalikan total dengan 3 setiap 4 penekanan tombol.

Menggunakan pola ini di sini adalah beberapa kode Python yang mendapatkan hasil yang sama dengan solusi marcog, tetapi O (1) edit : Ini sebenarnya adalah O (log n) karena eksponen, terima kasih kepada IVlad untuk menunjukkannya.

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)

Menghitung e3: Selalu ada antara 0 dan 4 pola SCPP di akhir daftar keystroke, karena n % 5 == 4ada 4, n % 5 == 1ada 3, n % 5 == 2ada 2, n % 5 == 3ada 1, dan n % 5 == 4ada 0. Ini dapat disederhanakan menjadi (4 - n) % 5.

Menghitung e4: Jumlah pola meningkat 1 setiap kali n % 5 == 0, ternyata jumlah ini meningkat persis n / 5. Menggunakan pembagian lantai kita bisa mendapatkan jumlah pola, jumlah totalnyae4 adalah jumlah pola dikurangi e3. Bagi mereka yang tidak terbiasa dengan Python, //adalah notasi bukti masa depan untuk pembagian lantai.

Inilah cara saya mendekatinya:

• asumsikan CtrlA= pilih semua
• asumsikan CtrlC= salin pilihan
• asumsikan CtrlV= tempel pilihan yang disalin

dengan beberapa teks, dibutuhkan 4 penekanan tombol untuk menduplikasinya:

• CtrlA untuk memilih semuanya
• CtrlC untuk menyalinnya
• CtrlV untuk menempel (ini akan menempel pada pilihan - NILAI ASUMSI ANDA)
• CtrlV untuk menempelkan lagi yang menggandakannya.

Dari sana, Anda dapat mempertimbangkan untuk melakukan 4 atau 5 A, lalu mengulang yang di atas. Perhatikan bahwa melakukan ctrl + a, c, v, vakan mengembangkan teks Anda secara eksponensial saat Anda mengulanginya. Jika sisa pukulan <4, terus lakukan aCtrlV

Kunci untuk mewawancarai @ tempat-tempat seperti Google adalah menyatakan asumsi Anda, dan mengomunikasikan pemikiran Anda. mereka ingin tahu bagaimana Anda memecahkan masalah.

Ini bisa diselesaikan dalam O (1): Seperti halnya angka Fibonacci, ada rumus untuk menghitung jumlah As yang dicetak (dan urutan penekanan tombol):

1) Kami dapat menyederhanakan deskripsi masalah:

• Hanya memiliki [A], [Ca] + [Cc], [Cv] dan buffer copy-paste yang kosong

sama

• hanya memiliki [Ca] + [Cc], [Cv] dan "A" di buffer salin-tempel.

2) Kita dapat mendeskripsikan urutan penekanan tombol sebagai string N karakter dari {'*', 'V', 'v'}, di mana 'v' berarti [Cv] dan '*' berarti [Ca] dan 'V 'berarti [Cc]. Contoh: "vvvv * Vvvvv * Vvvv"

Panjang tali itu masih sama dengan N.

Produk dari panjang kata-kata V dalam string itu sama dengan jumlah As yang dihasilkan.

3) Diketahui panjang tetap N untuk string itu dan sejumlah K kata tetap, hasilnya akan maksimal jika semua kata memiliki panjang yang hampir sama. Perbedaan pasangannya tidak lebih dari ± 1.

Sekarang, berapakah bilangan optimal K, jika N diberikan?

4) Misalkan, kita ingin menambah jumlah kata dengan menambahkan satu kata dengan panjang L, lalu kita harus mengurangi L + 1 kali kata sebelumnya dengan satu 'v'. Contoh: "… * Vvvv * Vvvv * Vvvv * Vvvv" -> "… * Vvv * Vvv * Vvv * Vvv * Vvv"

Sekarang, berapa panjang kata optimal L?

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

=> Optimal adalah L = 4.

5) Misalkan, kita memiliki N yang cukup besar untuk menghasilkan string dengan banyak kata dengan panjang 4, tetapi tersisa beberapa penekanan tombol; bagaimana kita harus menggunakannya?

• Jika tersisa 5 atau lebih: Tambahkan kata lain dengan panjang 4.

• Jika tersisa 0: Selesai.

• Jika ada 4 tersisa: Kita juga bisa

  a) tambahkan satu kata dengan panjang 3: 4 * 4 * 4 * 4 * 3 = 768.

  b) atau tambah 4 kata menjadi panjang 5: 5 * 5 * 5 * 5 = 625. => Menambahkan satu kata lebih baik.

• Jika ada 3 tersisa: Kita bisa

  a) atau tambahkan satu kata dengan panjang 3 dengan menyesuaikan kata sebelumnya dari panjang 4 menjadi 3: 4 * 4 * 4 * 2 = 128 <4 * 4 * 3 * 3 = 144.

  b) menambah 3 kata menjadi panjang 5: 5 * 5 * 5 = 125. => Menambahkan satu kata lebih baik.

• Jika ada 2 tersisa: Kita juga bisa

  a) atau tambahkan satu kata dengan panjang 3 dengan menyesuaikan sebelumnya dua kata dari panjang 4 menjadi 3: 4 * 4 * 1 = 16 <3 * 3 * 3 = 27.

  b) tambah 2 kata menjadi panjang 5: 5 * 5 = 25. => Menambahkan satu kata lebih baik.

• Jika ada 1 tersisa: Kita juga bisa

  a) atau tambahkan satu kata dengan panjang 3 dengan menyesuaikan tiga kata sebelumnya dari panjang 4 menjadi 3: 4 * 4 * 4 * 0 = 0 <3 * 3 * 3 * 3 = 81.

  b) menambah satu kata menjadi panjang 5: 4 * 4 * 5 = 80. => Menambahkan satu kata lebih baik.

6) Sekarang, bagaimana jika kita tidak memiliki "N cukup besar" untuk menggunakan aturan di 5)? Kami harus tetap berpegang pada rencana b), jika memungkinkan! String untuk N kecil adalah:

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

5: "vvvvv" → 5 (rencana b)

6: "vvvvvv" → 6 (rencana b)

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

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

9: "vvvv * Vvvv" → 16

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

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

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

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

14: "vvvv * Vvvv * Vvvv" → 64

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

…

7) Sekarang, berapakah jumlah K kata optimal dalam string dengan panjang N?

Jika N <7 maka K = 1 lain jika 6 <N <11 maka K = 2; jika tidak: K = ceil ((N + 1) / 5)

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

Dan jika N> 10, maka banyaknya kata dengan panjang 3 adalah: K * 5-1-N. Dengan ini, kita dapat menghitung jumlah cetakan As:

Jika N> 10, jumlah As akan menjadi: 4 ^ {N + 1-4K} · 3 ^ {5K-N-1}

Menggunakan CtrlA+ CtrlC+ CtrlVadalah keuntungan hanya setelah 4 'A.

Jadi saya akan melakukan sesuatu seperti ini (dalam pseudo-BASIC-code, karena Anda belum menentukan bahasa yang tepat):

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

Edit

1. Kembali menggunakan satu CtrlVdi loop utama.
2. Menambahkan beberapa komentar untuk menjelaskan apa yang saya coba lakukan di sini.
3. Memperbaiki masalah blok "empat A pertama".

Dibutuhkan 3 penekanan tombol untuk menggandakan jumlah As Anda. Masuk akal untuk mulai menggandakan ketika Anda memiliki 3 atau lebih As yang sudah dicetak. Anda ingin penekanan tombol terakhir Anda menjadi a CtrlVuntuk memastikan Anda menggandakan angka terbesar yang Anda bisa, jadi untuk menyelaraskannya, kami akan mengisi penekanan tombol tambahan setelah tiga As pertama di awal dengan lebih banyak 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");
}

Edit:

Ini mengerikan, saya benar-benar terlalu terburu-buru dan tidak mempertimbangkan banyak pasta untuk setiap salinan.

Edit 2:

Saya percaya menempelkan 3 kali itu optimal, ketika Anda memiliki cukup ketukan untuk melakukannya. Dalam 5 penekanan tombol, Anda mengalikan jumlah As dengan 4. Ini lebih baik daripada mengalikan dengan 3 menggunakan 4 tombol dan lebih baik daripada mengalikan dengan 5 menggunakan 6 penekanan tombol. Saya membandingkan ini dengan memberikan setiap metode jumlah penekanan tombol yang sama, cukup sehingga masing-masing akan menyelesaikan satu siklus pada waktu yang sama (60), membiarkan pengali 3 melakukan 15 siklus, pengali 4 melakukan 12 siklus, dan 5- pengganda melakukan 10 siklus. 3 ^ 15 = 14.348.907, 4 ^ 12 = 16.777.216, dan 5 ^ 10 = 9.765.625. Jika hanya ada 4 penekanan tombol yang tersisa, melakukan pengali 3 lebih baik daripada menempelkan 4 kali lebih banyak, pada dasarnya membuat 4 pengali sebelumnya menjadi pengali 8. Jika hanya ada 3 penekanan tombol yang tersisa, pengganda 2 adalah yang terbaik.

Asumsikan Anda memiliki karakter x di clipboard dan karakter x di area teks; sebut saja "state x".

Mari kita tekan "Tempel" beberapa kali (saya menandainya dengan m-1untuk kenyamanan), lalu "Pilih semua" dan "Salin"; setelah urutan ini, kita sampai ke "state m * x". Di sini, kami membuang total m + 1 penekanan tombol. Jadi pertumbuhan asimtotik (setidaknya) seperti f^n, di mana f = m^(1/(m+1)). Saya percaya itu adalah pertumbuhan asimtotik semaksimal mungkin, meskipun saya belum dapat membuktikannya.

Mencoba berbagai nilai m menunjukkan bahwa nilai maksimum untuk f diperoleh m=4.

Mari gunakan algoritma berikut:

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

(tidak yakin itu yang optimal).

Frekuensi menekan A di awal adalah 3: jika Anda menekannya 4 kali, Anda kehilangan kesempatan untuk menggandakan jumlah A dalam 3 penekanan tombol lagi.

Frekuensi untuk menekan Tempel di akhir tidak lebih dari 5: jika Anda memiliki 6 atau lebih tombol yang tersisa, Anda dapat menggunakan Tempel, Tempel, Tempel, Pilih-semua, Salin, Tempel sebagai gantinya.

Jadi, kami mendapatkan algoritma berikut:

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

(tidak yakin itu yang optimal). Jumlah karakter setelah menjalankan ini adalah seperti

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

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

Berikut ini menggunakan pengeditan kedua OP yang menempelkan tidak menggantikan teks yang ada.

Perhatikan beberapa hal:

• ^ A dan ^ C dapat dianggap sebagai tindakan tunggal yang membutuhkan dua kali penekanan tombol, karena tidak masuk akal untuk melakukannya secara individual. Faktanya, kita bisa mengganti semua contoh ^ A ^ C dengan ^ K ^ V, di mana ^ K adalah kunci satu operasi "potong" (mari kita singkatnya X). Kita akan melihat bahwa berurusan dengan ^ K jauh lebih baik daripada dua-biaya ^ A ^ C.
• Mari kita asumsikan bahwa 'A' dimulai di clipboard. Maka ^ V (disingkat Y) lebih unggul dari A dan kita bisa menghilangkan yang terakhir dari semua pertimbangan. (Dalam masalah sebenarnya, jika clipboard mulai kosong, selanjutnya kita hanya akan mengganti Y dengan A, bukan ^ V hingga X pertama.)

Dengan demikian, setiap urutan penekanan tombol yang wajar dapat diartikan sebagai sekelompok Y yang dipisahkan oleh X, misalnya YYYXYXYYXY. Dinyatakan dengan V (s) banyaknya 'A yang dihasilkan oleh barisan s. Kemudian V (nXm) = V (n) * V (m), karena X pada dasarnya menggantikan setiap Y dalam m dengan V (n) 'A.

Masalah salin-tempel dengan demikian isomorfik dengan masalah berikut: "menggunakan angka m + 1 yang berjumlah Nm, maksimalkan hasil kali mereka." Misalnya, jika N = 6, jawabannya adalah m = 1 dan angka (2,3). 6 = 2 * 3 = V (YYXYYY) = V (AA ^ A ^ C ^ V ^ V) (atau V (YYYXYY) = V (AAA ^ A ^ C ^ V).)

Kami dapat membuat beberapa pengamatan:

Untuk nilai tetapm , angka yang dipilih adalah ceil( (N-m)/(m+1) )dan floor( (N-m)/(m+1) )(dalam kombinasi apa pun yang membuat jumlah tersebut berhasil; lebih khusus lagi Anda akan membutuhkan (N-m) % (m+1) ceilsdan sisanya floor). Ini karena, untuk a < b,(a+1)*(b-1) >= a*b .

Sayangnya saya tidak melihat cara mudah untuk menemukan nilai m. Jika ini adalah wawancara saya, saya akan mengusulkan dua solusi pada saat ini:

Opsi 1. Ulangi semua kemungkinan m. n log nSolusi O ( ).

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

Opsi 2. Memungkinkan muntuk mencapai nilai non-integer dan menemukan nilai optimalnya dengan mengambil turunan dari [(N-m)/(m+1)]^msehubungan dengan mdan memecahkan akarnya. Tidak ada solusi analitik, tetapi akarnya dapat ditemukan menggunakan misalnya metode Newton. Kemudian gunakan lantai dan langit-langit dari akar tersebut untuk nilai m, dan pilih mana yang terbaik.

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

Inilah pendekatan dan solusi saya dengan kode di bawah ini.

Pendekatan:

Ada tiga operasi berbeda yang dapat dilakukan.

1. Keystroke A - Menghasilkan satu karakter 'A'
2. Keystroke (Ctrl-A) + (Ctrl-C) - Tidak menghasilkan apa-apa. Kedua penekanan tombol ini dapat digabungkan menjadi satu operasi karena masing-masing penekanan tombol ini secara individual tidak masuk akal. Selain itu, penekanan tombol ini mengatur keluaran untuk operasi tempel berikutnya.
3. Keystroke (Ctrl-V) - Output untuk keystroke ini sangat bergantung pada operasi (kedua) sebelumnya dan karenanya kita perlu memperhitungkannya dalam kode kita.

Sekarang mengingat tiga operasi yang berbeda dan keluarannya masing-masing, kita harus menjalankan semua permutasi dari operasi ini.

Anggapan:

Sekarang, beberapa versi masalah ini menyatakan bahwa urutan penekanan tombol, Ctrl + A -> Ctrl + C -> Ctrl + V, menimpa pilihan yang disorot. Untuk memperhitungkan asumsi ini, hanya satu baris kode yang perlu ditambahkan ke solusi di bawah ini di mana variabel yang dicetak dalam kasus 2 diatur ke 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;    
            }

Untuk solusi ini

Kode di bawah ini akan mencetak beberapa urutan dan urutan terakhir adalah jawaban yang benar untuk setiap N. misalnya untuk N = 11 ini akan menjadi urutan yang benar

Dengan asumsi

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

Tanpa asumsi

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

Saya telah memutuskan untuk mempertahankan asumsi untuk solusi ini.

Legenda Keystroke:

'A A

'C' - Ctrl + A

'S' - Ctrl + C

'V' - Ctrl + V

Kode:

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

Menggunakan trik yang disebutkan dalam jawaban di atas, Secara matematis, Solusi dapat dijelaskan dalam satu persamaan sebagai,

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5]. dimana [] adalah faktor integer terbesar

Ada trade-off antara mencetak mA secara manual, lalu menggunakan Ctrl+ A, Ctrl+ C, dan Nm-2 Ctrl+ V. Solusi terbaik ada di tengah. Jika penekanan tombol maks = 10, solusi terbaik adalah mengetikkan 5 A atau 4 A.

coba gunakan ini Lihat ini http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ dan mungkin optimalkan sedikit mencari hasil sekitar pertengahan titik.

Inilah solusi saya dengan pemrograman dinamis, tanpa loop bersarang, dan yang juga mencetak karakter sebenarnya yang perlu Anda ketik:

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

Ini adalah outputnya ('a' berarti 'CTRL + A', dll.)

 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 

Jika N key Stroke diperbolehkan, maka hasilnya adalah N-3.

A -> N-3

CTRL+ A-> Memilih Karakter N itu: +1

CTRL+ C-> Menyalin Karakter N itu: +1

Ctrl+ V-> Menempelkan Karakter N. : +1 yaitu, (Karena kita telah memilih seluruh karakter menggunakan CTRL+ A) Mengganti karakter N-3 yang ada ini dengan Karakter N-3 yang disalin (yang menimpa karakter yang sama) dan hasilnya adalah N-3.