Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As saikat has pointed out, this is incorrect.
According to me:
*buff = 0; //keeps track of last ctrlC*
> *for each i*
> *{*
> * dp(i)=max(dp(i-1)+1, 2*dp(i-3), dp(i-1) + buff)*
> * if(dp(i)==2*dp(i-3)) { buff = dp(i-3);}*
> *}*
>
@saikat: for n=10, this gives dp(10) = 20 :D
An O(n) soln.
Cheers
Nikhil Jindal
Delhi College of Engineering (DCE),
Delhi.
On Wed, Jan 19, 2011 at 10:05 PM, nishaanth <nishaant...@gmail.com> wrote:
> How about the following dynamic programming solution.
>
> Let dp[i] be the max no of As with i keystrokes.
>
> dp[i]=max(dp[i-1]+1,2*dp[i-3])
>
> dp[N] is the required solution.
>
> Correct me if i am wrong.
>
>
> On Wed, Jan 19, 2011 at 9:20 PM, Raj <rajmangaltiw...@gmail.com> wrote:
>
>> http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
>>
>> On Jan 19, 8:28 pm, bittu <shashank7andr...@gmail.com> wrote:
>> > Given
>> >
>> > 1. A
>> > 2. Ctrl+A
>> > 3. Ctrl+C
>> > 4. Ctrl+V
>> >
>> > 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.
>> >
>> > So the input parameter is N (No. of keys that you can press), the
>> > output is M (No. of As that you can produce).
>> >
>> > Thanks & Regards
>> > Shashank Mani
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
