wu :: forums - Print Page


    
      
        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 8^th, 2011, 11:45pm)

Title: Ctrl+A Ctrl+C Ctrl+V
Post by inexorable on Apr 8^th, 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 9^th, 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 9^th, 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 19^th, 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 20^th, 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 4^th, 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 4^th, 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 4^th, 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

A^a SC V^b SC V^c SC V^d SC V^e (SC V⁴)^x, giving a score of a*b*c*d*e*4^x
(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 6^th, 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 6^th, 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 26^th, 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

Please rectifiy

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by towr on Mar 26^th, 2014, 11:29am

In this version the first paste overwrites the selection, so it is correct as it is.
Just open notepad and follow the instructions, and you'll get 12.

Title: Re: Ctrl+A Ctrl+C Ctrl+V
Post by birbal on Nov 25^th, 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 25^th, 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 A
2. S after A
3. C after S
4. V after C
5. V after V
6. 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