Extension to a standard dp problem :)

Правка en1, от Heisenberg, 2017-08-22 12:42:54

Given 1<= n <= 10^6. At every stage one can apply any one of three operations : (1.) if i%3==0 then i=i/3; (2.) if i%2==0 then i=i/2; (3.) if i>=1 then i=i-1; --------->The target is to apply the above steps till we reach 1 ; We can find minimum number of steps to reach 1 easily by simple dp state !! --------->But what if we need to check whether this can be done in exactly k steps where 0<=k<=n-1. ---------->For Example : 1.{ n=10; if(k==4) ans= yes.(10->9->3->1) if(k==3) ans= no. } Solution Needed !!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Heisenberg 2017-08-22 12:42:54 586 Initial revision (published)