Как напечатать максимальное количество букв A, используя заданные четыре клавиши


Сложный уровень средний
Часто спрашивают в Амазонка Facebook Google PayPal Paytm
Динамическое программирование

Постановка задачи

Как напечатать максимальное количество букв A с помощью заданных четырех клавиш, эта проблема заключается в том, что у вас есть возможность выбрать, какую клавишу нажимать. Ключи выполняют следующие задачи:

  1. Key1 - печатает букву A на экране.
  2. Key2 - Выбрать весь экран.
  3. Key3 - копировать выбранный контент.
  4. Key4 - Распечатать скопированный контент.

Вы можете нажимать клавиши только N раз, узнайте максимальное количество A, которое можно напечатать. Используя любую из возможных комбинаций, найдите максимальное количество букв A, которое можно напечатать.

Пример

Number of keys that can be pressed = 2
Number of A's that can be printed = 2

Объяснение: Поскольку никакая другая комбинация не даст лучшего результата. Используя любую другую комбинацию нажатий клавиш, вы не сможете напечатать большее количество букв A. Можем попробовать любую другую комбинацию. Допустим, мы печатаем один A. Потому что, если мы не напечатаем «A», мы не сможем выбрать «A» и затем распечатать его. Так что лучше вывести единственную букву «А». После этого мы можем выполнить любую из трех комбинаций: выбор, печать и копирование. Но ни одна из этих комбинаций не даст лучших результатов.

Как напечатать максимальное количество букв A, используя заданные четыре клавиши

Number of keys that can be pressed = 6
Number of A's that can be printed = 6

Объяснение: Мы будем использовать следующие 6 нажатий клавиш: Key1 (печатает «A»), Key1, Key1, Key2 (выбирает все содержимое экрана), Key3 (копирует выбранный контент), Key4 (печатает скопированное содержимое). Могут быть и другие нажатия клавиш, которые могут напечатать такое же количество букв A.

Подход

Найти, как напечатать максимальное количество A с использованием заданных четырех клавиш, можно решить, если мы начнем с количества нажатий клавиш = N-3 до 1 и попытаемся найти максимальное количество A.
Мы будем считать, что i-я позиция - это точка, откуда мы нажимаем Key2, Key3, а затем последовательность Key4. Теперь, если мы перейдем от N-3 к 1. Таких точек может быть много.

Как всегда, нам нужен базовый вариант, потому что проблема использует динамическое программирование. Здесь случай, когда n <= 6, мы просто печатаем число. Почему мы называем это динамическое программирование даже если в коде мы не используем какой-либо массив DP? Потому что задача удовлетворяет двум условиям: перекрывающиеся подзадачи и оптимальная подструктура. Каждую проблему можно подразделить на более мелкие, а затем разделить.

Код:

Код на C ++ для поиска максимального количества As, которое может быть напечатано

#include <bits/stdc++.h>
using namespace std;

int maximumNumberOfAsPrinted(int numberOfKeyPresses)
{
  if(numberOfKeyPresses <= 6)
    return numberOfKeyPresses;

  int maxNumberOfAs = 0;
  for(int i = numberOfKeyPresses-3; i>=1;i--) {
    // here we consider that after ith keystroke we are performing only selection, copy once and then paste
    // thus starting from numberOfKeyPresses-3
    int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    if (numberOfAs > maxNumberOfAs)
      maxNumberOfAs = numberOfAs;
  }
  return maxNumberOfAs;
}

int main()
{
  int numberOfKeyPresses;cin>>numberOfKeyPresses;
  int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
  cout<<numberOfAsPrinted;
}
18
192

Код Java, чтобы найти максимальное количество As, которое может быть напечатано

import java.util.*;

class Main{
    static int maximumNumberOfAsPrinted(int numberOfKeyPresses)
    {
    	if(numberOfKeyPresses <= 6)
    		return numberOfKeyPresses;
    
    	int maxNumberOfAs = 0;
    	for(int i = numberOfKeyPresses-3; i>=1;i--) {
    		// here we consider that after ith keystroke we are performing only selection, copy once and then paste
    		// thus starting from numberOfKeyPresses-3
    		int numberOfAs = (numberOfKeyPresses-i-1)*maximumNumberOfAsPrinted(i);
    		if (numberOfAs > maxNumberOfAs)
    			maxNumberOfAs = numberOfAs;
    	}
    	return maxNumberOfAs;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
    	int numberOfKeyPresses = sc.nextInt();
    	int numberOfAsPrinted = maximumNumberOfAsPrinted(numberOfKeyPresses);
    	System.out.println(numberOfAsPrinted);
    }
}
18
192

Анализ сложности

Сложность времени: НА)

Поскольку мы просто запустили цикл по нескольким нажатиям клавиш. Алгоритм имеет линейную временную сложность O (N).

Космическая сложность: O (1)

Поскольку мы храним только некоторые конкретные целые числа и элементы. У нас постоянная космическая сложность.