wu :: forums « wu :: forums - Ctrl+A Ctrl+C Ctrl+V » Welcome, Guest. Please Login or Register. May 19th, 2024, 11:30am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: ThudnBlunder, SMQ, towr, Grimbal, william wu, Eigenray, Icarus)    Ctrl+A Ctrl+C Ctrl+V « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Ctrl+A Ctrl+C Ctrl+V  (Read 6871 times)
inexorable
Full Member

Posts: 211
 Ctrl+A Ctrl+C Ctrl+V   « on: Apr 8th, 2011, 11:45pm » Quote Modify

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 }.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #1 on: Apr 9th, 2011, 3:31am » Quote Modify

Sounds like this topic
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #2 on: Apr 9th, 2011, 5:10am » Quote Modify

Yes, but the examples in this version get the "first paste overwrites the selection" part right and so represent real-world computer behavior.

--SMQ
 IP Logged

--SMQ

kalni
Newbie

Gender:
Posts: 1
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #3 on: Jun 19th, 2011, 1:15pm » Quote Modify

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
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #4 on: Jun 20th, 2011, 9:03am » Quote Modify

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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
kumariitr
Newbie

Posts: 4
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #5 on: Jul 4th, 2011, 4:14am » Quote Modify

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)
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #6 on: Jul 4th, 2011, 10:44am » Quote Modify

That's rather doubtful, but more importantly, how would you proceed with the 'c-A,c-C's and 'c-V's?
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #7 on: Jul 4th, 2011, 11:50am » Quote Modify

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).
 « Last Edit: Jul 6th, 2011, 8:53am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
kumariitr
Newbie

Posts: 4
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #8 on: Jul 6th, 2011, 1:36am » Quote Modify

after calculating nA, type A's "nA" times and then c-A, c-C and then after remaining will be c-V
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #9 on: Jul 6th, 2011, 8:52am » Quote Modify

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.
 « Last Edit: Jul 6th, 2011, 9:10am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
bisht_1991
Newbie

Gender:
Posts: 1
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #10 on: Mar 26th, 2014, 10:33am » Quote Modify

for n=9

its printing

15 A's

that is

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

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #11 on: Mar 26th, 2014, 11:29am » Quote Modify

In this version the first paste overwrites the selection, so it is correct as it is.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member

Gender:
Posts: 250
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #12 on: Nov 25th, 2014, 4:19pm » Quote Modify

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).

 IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Ctrl+A Ctrl+C Ctrl+V   « Reply #13 on: Nov 25th, 2014, 10:37pm » Quote Modify

on Nov 25th, 2014, 4:19pm, 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
 « Last Edit: Nov 25th, 2014, 10:42pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »