### Problem

Imagine you have a special keyboard with the following keys:A

Ctrl+A

Ctrl+C

Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.

That is to say, the input parameter is

**N**(No. of keys that you can press), the output is

**M**(No. of A's that you can produce).

### Solution

One common strategy in problem solving is to always begin with small examples.

It is trivial to notice that for

*N*<= 6,

*M*=

*N*. But how about the case where

*N*= 7?

Here is where the most common pitfall that most people would fall into (myself included).

Most people reason that for

*N*= 7, the answer is

*M*= 8, because the sequence

*S*= { A, A, A, A, CTRL+A, CTRL+C, CTRL+V } produces a total of 8 A’s.

Wait, the copied text is still in the buffer after a paste operation. We could have applied CTRL+V twice to double the previous text, sweet!

How about

*S*= { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V } which produces a total of 9 A’s?

Unfortunately, both of the above answers are incorrect, as the correct answer for

*N*= 7 is

*M*= 7. This is simply because the sequence of { CTRL+A, CTRL+C, CTRL+V } does not double the previous text. Why? Take a moment to let this to sink into your brain.

Answers for

*N*up to 7 is easy, which is

*M*=

*N*. But how about

*N*= 8?

For

*N*= 8 the answer is

*M*= 9, where

*S*= { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V }.

For

*N*= 9 the answer is

*M*= 12, where

*S*= { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V, CTRL+V }.

Now lets following notation:

- Define
**4A**as a sequence of { A, A, A, A }. Therefore,**5A**would then mean { A, A, A, A, A }. - Define
**2D**as a sequence of CTRL+A, CTRL+C, CTRL+V, CTRL+V, which simply means*double the previous text*. Note that**3D**does not double the previous text, it actually triples the previous text.

*N*= 8 and

*N*= 9.

*N*= 8,

*S*= {

**3A3D**},

*M*= 9.

*N*= 9,

*S*= {

**3A4D**},

*M*= 12.

The value of M could be obtained simply by multiplying the numbers, isn’t that neat?

Working our way up:

*N*= 10,

*S*= {

**4A4D**},

*M*= 16.

*N*= 11,

*S*= {

**5A4D**},

*M*= 20.

As you can see, the pattern here is pretty obvious, let’s summarize as follow:

- The solution so far for
*N*> 7 is to find integers*a*and*b*such that*ab*yields the largest product, subjected to the condition where*a*+*b*=*N*-2. - Both
*a*and*b*are easy to find, as the largest product is found when the difference of*a*and*b*is less than or equal to one.

*N*= 12,

*S*= {

**5A5D**},

*M*= 25.

*N*= 13,

*S*= {

**5A6D**},

*M*= 30.

*N*= 14,

*S*= {

**6A6D**},

*M*= 36.

Be extra cautious for

*N*= 15.

When

*N*= 15, does the sequence {

**6A7D**} yields the maximum where

*M*= 42?

Imagine if you have a very large number of keystrokes to enter, does pressing CTRL+V forever gives you the maximum sequence? Remember, you can redo the entire { CTRL+A, CTRL+C, CTRL+V } operations again and potentially maximizes the sequence.

For

*N*= 15, the maximum sequence should be:

{

**3A4D4D**}, which yields

*M*= 48.

Similarly,

*N*= 16,

*S*= {

**4A4D4D**},

*M*= 64.

…

*N*= 21,

*S*= {

**3A4D4D4D**},

*M*= 192.

…

*N*= 25,

*S*= {

**4A5D5D5D**},

*M*= 500.

*N*= 26,

*S*= {

**5A5D5D5D**},

*M*= 625.

*N*= 27,

*S*= {

**3A4D4D4D4D**},

*M*= 768.

Let’s generalize the above:

*M*= MAX (

*a*

_{1}.

*a*

_{2}…

*a*),where

_{k}

a

a

_{1}+

*a*

_{2}+ … +

*a*

_{k}=

*n*– 2(

*k*-1)

*M*= MAX (

*a*

_{1}.

*a*

_{2}…

*a*

_{k}),

it is necessary that the below condition must be met:

∀

To obtain *i*,*j*∈{ 1, 2, … ,*k*} : MAX ( |*a*–_{i}*a*| ) = 1._{j}*M*, we can first divide

*a*

_{1}+

*a*

_{2}+ … +

*a*by

_{k}*k*to obtain the average as a reference, and the rest should be straightforward.

Now the final problem lies in how to obtain the value of

*k*efficiently. I am pretty sure this could be solved easily using Number Theory, but so far, my best solution is to use a brute force method to obtain

*k*.

Here is a solution using DP

public static int maxChar(int n) { int[] dp = new int[n]; for (int i = 0; i < n; ++i) { dp[i] = i + 1; // type A } for (int i = 0; i < n; ++i) { for (int j = i + 4; j < n; ++j) { dp[j] = Math.max(dp[j], dp[i] * (j - i - 3)); // using Ctrl + V } } return dp[n - 1]; }

**References**

- http://www.careercup.com/question?id=7184083
- http://leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html
- http://shawnxublog.blogspot.in/2013/03/ctrla-ctrlc-ctrlv.html

Code given by does not give desired output.. please check the code given below working fine.

ReplyDeleteint MaxCopy(int n){

int *table=(int *)malloc(sizeof(int)*(n+1));

memset(table,0,sizeof(int)*(n+1));

for(int i=0;i<=n;i++){

table[i]=i;

}

for(int i=0;i<=n;i++){

for(int j=i+4;j<=n;j++){

table[j]=max(table[j],table[i]*(j-i-2));

}

}

int res=table[n];

free(table);

return res;

}

Thanks man for fixing it. I will update it soon.

ReplyDelete