Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There's a dynamic programming solution. We start off knowing 0 keys can make us 0 A's. Then we iterate through for <code>i</code> up to <code>n</code>, doing two things: pressing A once and pressing select all + copy followed by paste <code>j</code> times (actually <code>j-i-1</code> below; note the trick here: the contents are still in the clipboard, so we can paste it multiple times without copying each time). We only have to consider up to 4 consecutive pastes, since select, copy, paste x 5 is equivalent to select, copy, paste, select, copy, paste and the latter is better since it leaves us with more in the clipboard. Once we've reached <code>n</code>, we have the desired result.</p> <p>The complexity might appear to be O(N), but since the numbers grow at an exponential rate it is actually O(N<sup>2</sup>) due to the complexity of multiplying the large numbers. Below is a Python implementation. It takes about 0.5 seconds to calculate for N=50,000.</p> <pre><code>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] </code></pre> <p>In the code, <code>j</code> represents the total number of keys pressed after our new sequence of keypresses. We already have <code>i</code> keypresses at this stage, and 2 new keypresses go to select-all and copy. Therefore we're hitting paste <code>j-i-2</code> times. Since pasting adds to the existing sequence of <code>dp[i]</code> <code>A</code>'s, we need to add <code>1</code> making it <code>j-i-1</code>. This explains the <code>j-i-1</code> in the 2nd-last line.</p> <p>Here are some results (<code>n</code> => number of A's):</p> <ul> <li>7 => 9</li> <li>8 => 12</li> <li>9 => 16</li> <li>10 => 20</li> <li>100 => 1391569403904</li> <li>1,000 => 3268160001953743683783272702066311903448533894049486008426303248121757146615064636953144900245 174442911064952028008546304</li> <li>50,000 => <a href="http://pastebin.com/FPJU3VP2" rel="noreferrer">a very large number!</a></li> </ul> <p>I agree with @SB that you should always state your assumptions: Mine is that you don't need to paste twice to double the number of characters. This gets the answer for 7, so unless my solution is wrong the assumption must be right.</p> <p>In case someone wonders why I'm not checking sequences of the form <kbd>Ctrl</kbd>+<kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>C</kbd>, <kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>V</kbd>: The end result will always be the same as <kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>A</kbd>, <kbd>Ctrl</kbd>+<kbd>C</kbd>, <kbd>Ctrl</kbd>+<kbd>V</kbd> which I <em>do</em> consider.</p>
    singulars
    1. This table or related slice is empty.
    1. POMaximum number of characters using keystrokes A, Ctrl+A, Ctrl+C and Ctrl+V
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USHulk1991
    1. USmarcog
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUndeletion
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIs that `n => result` or `result => n`? Either way, I think it's wrong. We can type 9 As with 7 keystrokes. If it's `n => result` it's definitely wrong. The number of As you can type cannot be lower than `n`.
      singulars
      1. PO
      1. USIVlad
    2. CO@IVlad It's `n => result`. You say "We can type 9 As with 7 keystrokes", which is what I get. Read the "trick" I just edited in.
      singulars
      1. PO
      1. USmarcog
    3. COThis looks great, except that the question is to find the maximum number of As for a given number of keystrokes, not the minimum number of keystrokes to get a given number of As.
      singulars
      1. PO
      1. USAndrew Clark
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload