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 Home Help Help Search Search Members Members Login Login Register 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print 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 Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #1 on: Apr 9th, 2011, 3:31am »
Quote Quote Modify Modify

Sounds like this topic
IP Logged

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






   


Gender: male
Posts: 2084
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #2 on: Apr 9th, 2011, 5:10am »
Quote Quote Modify 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: male
Posts: 1
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #3 on: Jun 19th, 2011, 1:15pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #4 on: Jun 20th, 2011, 9:03am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #6 on: Jul 4th, 2011, 10:44am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #7 on: Jul 4th, 2011, 11:50am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #9 on: Jul 6th, 2011, 8:52am »
Quote Quote Modify 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: male
Posts: 1
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #10 on: Mar 26th, 2014, 10:33am »
Quote Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #11 on: Mar 26th, 2014, 11:29am »
Quote Quote Modify 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: male
Posts: 250
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #12 on: Nov 25th, 2014, 4:19pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Ctrl+A Ctrl+C Ctrl+V  
« Reply #13 on: Nov 25th, 2014, 10:37pm »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board