@ Nikhil sir : I have coded the same solution, but was waiting for its correctness to be proved... thanx.. :)
On Fri, Jan 28, 2011 at 1:01 PM, Nikhil Jindal <[email protected]>wrote: > 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 <[email protected]> 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 <[email protected]> wrote: >> >>> http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html >>> >>> On Jan 19, 8:28 pm, bittu <[email protected]> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > > To unsubscribe from this group, send email to > [email protected] > <algogeeks%[email protected]>. > > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- Regards Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
