Recently I've found an interesting puzzle, algorithmic one.

Eventually I solved it (thanks to my smart wife's idea). You're welcome with your ideas how to solve it in comments. But please make sure you've added clear explanation to your code or idea.

UPDATE 2/9/2011

Thanks to all of you guys who tried to solve the puzzle and shared your ideas in comments. As the correct solution appears in comments (thanks to Guest), I decided to publish my own solution/explanation as well. Apparently the most straightforward solution is to use dynamic programming, to calculate maximum sum of A’s. But let’s consider the following assumptions before we get to the algorithm:

1. Let’s say CTRL+A = S(elect), CTRL+C=C(opy), CTRL+V = P(aste) for short.

2. SCP sequence doesn’t increase existing amount of A’s, because the paste will override selected text with the same amount of A’s.

3. Let’s say we have K symbols in notepad at some point of time, next step we can do SCP and put K symbols to the buffer. Obviously next step should be Paste, as it doesn’t make sense to put the same amount of symbols to the buffer one more time.

So we have 2K in notepad and K in the buffer. Next let’s consider two possible scenarios:

OR

As you can see, eventually we will have the same amount of symbols in notepad. So we can conclude that SCPPPP and PPPPPP are equal in terms of final amount of A’s, but we’d prefer first case because it doubles value in buffer. From here - we need to calculate only 6 steps ahead and consider either first or second case, depending on what is bigger.

Each iteration we will take a look seven steps ahead and consider the following steps:

SCPP (first, which make sense for our goal)

SCP PP

SCP PPP

Compare them to steps we choose on previous iterations. Here is the code listing in C#

static int calc(int n)
{
    int[] r = new int[n + 1];
    for (int i = 0; i < n; i++)
    {
        r[i + 1] = Math.Max(r[i] + 1, r[i + 1]);//press one more A or leave it as is
        //consider SCPP option
        //it doesn’t make sense to paste from buffer more than 2 times after SCPP, because after SCPPPP we will consider new fork of solutions
        for (int j = i+4; j < Math.Min(i + 6, n + 1); j++)
        {
            //get the best option from the current one and SC + (j - i - 2) * P
            r[j] = Math.Max(r[j], r[i]*(j - i - 2));
        }
    }
    return r[n];//total sum
}

As Guest noted in comments, after N >= 28 we may see some sort of pattern

See simplified solution from Guest in comments. Although I wouldn’t use the knowledge of the pattern, just based on some subset of results. It’s better to prove it mathematically first.

Anyway, this puzzle looks absorbing. I had fun, hope you too.