```

wu :: forums
(http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)

riddles >> cs >> Ctrl+A Ctrl+C Ctrl+V
(Message started by: inexorable on Apr 8th, 2011, 11:45pm)

```

Title: Ctrl+A Ctrl+C Ctrl+V
Post by inexorable on Apr 8th, 2011, 11:45pm
Imagine you have a special keyboard with the following keys:

1. A
2. Ctrl+A
3. Ctrl+C
4. 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 As that you can produce).

Example:-
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 }.

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Apr 9th, 2011, 3:31am
Sounds like this topic (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1295541596)

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by SMQ on Apr 9th, 2011, 5:10am
Yes, but the examples in this version get the "first paste overwrites the selection" part right and so represent real-world computer behavior.

--SMQ

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by kalni on Jun 19th, 2011, 1:15pm
Say you press 'A', X number of times.
That leaves you with N-X key presses. You then press
ctrl-A,ctrl-C which leaves you with N-X-2 presses. You then press ctrl-V that many times.

No. of 'A's you get = (N-X-2)*X = (N-2)*X-X^2 = F(X)
To max this, its differential has to be 0.
Hence, F'(X) = N-2-2X = 0,
which means X = floor((N-2)/2) for 'A's to be maximum.

for N = 8, X = 3, max 'A's = 3*3 = 9
for N = 9, X = 3 again, max 'A's = 4*3 = 12

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Jun 20th, 2011, 9:03am
That doesn't give you the optimum for higher N. Just repeating c-A,c-C,c-V,c-V after the initial A already grows exponentially, which is much better than the quadratic growth you get.
The actual solution will probably be very similar to that of the problem in the other thread.

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by kumariitr on Jul 4th, 2011, 4:14am
nA = no. of A's we type intially
then we have to maximize (N-2-nA)*nA, and variable is nA. Which will give a simple solution nA = floor((N-2)/2)

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Jul 4th, 2011, 10:44am
That's rather doubtful, but more importantly, how would you proceed with the 'c-A,c-C's and 'c-V's?

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Jul 4th, 2011, 11:50am
If my pattern recognition ability is not off, from N=28 onwards, the pattern to maximize the number of A's is given by

m = (n-28) % 6
a = 4 + (m>=1)
b = 4 + (m>=2)
c = 4 + (m>=3)
d = 4 + (m>=4)
e = 4 + (m>=5)
x = (n-28) div 6

Aa SC Vb SC Vc SC Vd SC Ve (SC V4)x, giving a score of a*b*c*d*e*4x
(Where A = A, C = ctrl-C, V = ctrl-V, S = ctrl-A)

The maximum number of initial A's that's ever optimal is 7, for N=7, with 6 occurring 4 times (for N=6, 13, 14, 20).

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by kumariitr on Jul 6th, 2011, 1:36am
after calculating nA, type A's "nA" times and then c-A, c-C and then after remaining will be c-V

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Jul 6th, 2011, 8:52am
Well, for N = 50, I get a score of 160000, with A-A-A-A-A-S-C-V-V-V-V-V-S-C-V-V-V-V-V-S-C-V-V-V-V-V-S-C-V-V-V-V-S-C-V-V-V-V-S-C-V-V-V-V-S-C-V-V-V-V

Your solution would be A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-A-S-C-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V-V with a score of 576
It does give an optimal solution when N is between 8 and 14 (inclusive), though.

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by bisht_1991 on Mar 26th, 2014, 10:33am
for n=9

its printing

15 A's

that is

3-A's the Ctrl+A+C+V  then 3times ctrl+v

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Mar 26th, 2014, 11:29am
In this version the first paste overwrites the selection, so it is correct as it is.

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by birbal on Nov 25th, 2014, 4:19pm
Correct me if i am wrong in this, after a sufficiently long sequence, we will just need S, C, V and not As (as the benefit we get from A is fixed).

Also only allowed (or meaningful ) key presses, based on previous presses will be following :

1. A after A
2. S after A
3. C after S
4. V after C
5. V after V
6. A after V

Lets represent state of the output at any point using i key presses with three numbers ( Total As, Selected As, Copied As ) = ( X, Y, Z )

State i+1 can be { (X+1, 0, 0), ( X, X, Z), (X, 0, Y), (X+Z, 0, Z) }

Going by the actual value and doing meaningful operation, a lot of states will get pruned. As an example, a state where X != Y is not possible in our setup. For a state (X, 0, 0), next state can be only one of { (X+1, 0, 0), (X, X, 0) }. Next state to this can be { (X+2, 0, 0), (X+1, X+1, 0), (X, 0, X) }. The number of meaningful possible states should be O(N).

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Nov 25th, 2014, 10:37pm

on 11/25/14 at 16:19:19, birbal wrote:
 Correct me if i am wrong in this, after a sufficiently long sequence, we will just need S, C, V and not As (as the benefit we get from A is fixed).
That's right, in fact you never have to type an A except at the very start.

Quote:
 Also only allowed (or meaningful ) key presses, based on previous presses will be following :1. A after A2. S after A3. C after S4. V after C5. V after V6. A after V
I don't think the last one is never meaningful.

Quote:
 Lets represent state of the output at any point using i key presses with three numbers ( Total As, Selected As, Copied As ) = ( X, Y, Z )State i+1 can be { (X+1, 0, 0), ( X, X, Z), (X, 0, Y), (X+Z, 0, Z) }
Why would typing an A clear the paste buffer? And you seem to ignore that the first paste replaces the selected text.
I think it should be { (Y==0) * X+1, 0, Z), ( X, X, Z), (X, Y, Y), ((Y==0) * X+Z, 0, Z) }

Quote:
 Going by the actual value and doing meaningful operation, a lot of states will get pruned. As an example, a state where X != Y is not possible in our setup.
?!?
After every C (with non-empty paste buffer) or A you'll have X > 0 and Y == 0; and therefore X != Y