title: Maximum number of characters using keystrokes A, Ctrl+A, Ctrl+C and Ctrl+V
body: <p>This is an interview question from google. I am not able to solve it by myself. Can somebody shed some light?</p>
  
  <p>Write a program to print the sequence of keystrokes such that it generates the maximum number of character 'A's. You are allowed to use only 4 keys: <kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>C</kbd> and <kbd>Ctrl</kbd>+<kbd>V</kbd>. Only N keystrokes are allowed. All <kbd>Ctrl</kbd>+ characters are considered as one keystroke, so <kbd>Ctrl</kbd>+<kbd>A</kbd> is one keystroke.</p>
  
  <p>For example, the sequence <kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>C</kbd>, <kbd>Ctrl</kbd>+<kbd>V</kbd> generates two A's in 4 keystrokes.</p>
  
  <ul>
  <li>Ctrl+A is Select All</li>
  <li>Ctrl+C is Copy</li>
  <li>Ctrl+V is Paste</li>
  </ul>
  
  <p>I did some mathematics. For any N, using x numbers of A's , one <kbd>Ctrl</kbd>+<kbd>A</kbd>, one <kbd>Ctrl</kbd>+<kbd>C</kbd> and y <kbd>Ctrl</kbd>+<kbd>V</kbd>, we can generate max ((N-1)/2)<sup>2</sup> number of A's. For some N > M, it is better to use as many <kbd>Ctrl</kbd>+<kbd>A</kbd>'s, <kbd>Ctrl</kbd>+<kbd>C</kbd> and <kbd>Ctrl</kbd>+<kbd>V</kbd> sequences as it doubles the number of A's.</p>
  
  <p>The sequence <kbd>Ctrl</kbd>+<kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>V</kbd>, <kbd>Ctrl</kbd>+<kbd>C</kbd> will not overwrite the existing selection. It will append the copied selection to selected one.</p>