Author |
Topic: Ctrl+A Ctrl+C Ctrl+V (Read 6861 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 |
|
|
|
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
Please rectifiy
|
|
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.
Just open notepad and follow the instructions, and you'll get 12.
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print