Максимальное количество символов с использованием нажатий клавиш A, Ctrl + A, Ctrl + C и Ctrl + V

Question

Это вопрос интервью от Google.Я не могу решить это самостоятельно.Может кто-нибудь пролить свет?

Напишите программу для печати последовательности нажатий клавиш таким образом, чтобы она генерировала максимальное количество символов «А».Вам разрешено использовать только 4 клавиши: A , Ctrl + A , Ctrl + C и Ctrl + V * * 1016.Допускается только N нажатий клавиш.Все символы Ctrl + считаются одним нажатием клавиши, поэтому Ctrl + A - это одно нажатие клавиши.

Например, последовательность A , Ctrl + A , Ctrl + C , Ctrl + V генерирует два А за 4 нажатия клавиш.

• Ctrl + A - Выбрать все
• Ctrl + C - Копировать
• Ctrl + V - Вставить

Я занимался математикой.Для любого N, используя x чисел A, один Ctrl + A , один Ctrl + C и y Ctrl + V , мы можем сгенерировать максимальное ((N-1) / 2) ² количество A.Для некоторого N> M лучше использовать столько Ctrl + A , Ctrl + C и Ctrl + V последовательности, так как это удваивает число A.

Последовательность Ctrl + A , Ctrl + V , Ctrl + C не будет перезаписывать существующий выбор.Это добавит скопированный выбор к выбранному.

Answer 1

Существует компромисс между печатью мА вручную, затем с использованием Ctrl + A , Ctrl + C , и Nm-2 Ctrl + V . Лучшее решение в середине. Если максимальное количество нажатий клавиш = 10, лучшее решение - набрать 5 или 4.

попробуйте использовать это. Посмотрите на это http://www.geeksforgeeks.org/how-to-print-maximum-number-of-a-using-given-four-keys/ и, возможно, немного оптимизируйте, ища результаты около средней точки.

Answer 2

Используя уловки, упомянутые в ответах выше, математически решение можно объяснить одним уравнением:

4 + 4 ^ [(N-4) / 5] + ((N-4)% 5) * 4 ^ [(N-4) / 5].где [] - наибольшее целое число

Answer 3

Вот мой подход и решение с кодом ниже.

Подход:

Существует три отдельных операции, которые можно выполнить.

1. нажатие клавиши A - выводит один символ 'A'
2. нажатие клавиши (Ctrl-A) + (Ctrl-C) - по сути ничего не выводит. Эти два нажатия клавиш могут быть объединены в одну операцию, потому что каждое из этих нажатий клавиш по отдельности не имеет смысла. Кроме того, это нажатие клавиши настраивает вывод для следующей операции вставки.
3. Нажатие клавиши (Ctrl-V) - Выходные данные для этого нажатия клавиши действительно зависят от предыдущей (второй) операции и, следовательно, мы должны учитывать это в нашем коде.

Теперь, учитывая три различных операции и их соответствующие выходы, мы должны пройти через все перестановки этих операций.

---

Предположение:

Теперь в некоторых версиях этой проблемы говорится, что последовательность нажатий клавиш Ctrl + A -> Ctrl + C -> Ctrl + V перезаписывает выделенный фрагмент. Чтобы учесть это предположение, к приведенному ниже решению необходимо добавить только одну строку кода, где для печатной переменной в случае 2 задано значение 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;    
            }

Для этого решения

Приведенный ниже код напечатает пару последовательностей, и последняя последовательность является правильным ответом для любого заданного N., например, для N = 11 это будет правильная последовательность

С предположением

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

Без предположения

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

Я решил сохранить предположение для этого решения.

---

Легенда нажатия клавиш:

'A' - A

'C' - Ctrl + A

'S' - Ctrl + C

'V' - Ctrl + V

---

Код:

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

Answer 4

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