最小ステップ（バリアント）

Question

は、あなたは、これらの操作のいずれかを実行させます。

3-もしXは3の倍数は、あなたがでXを分割することができている3

私は問題のO（n）のDPソリューションがあると思うが、どのように1 < = X <のためにそれを解決するために= 10^9？

Answer 1

一挙一動があるように、これは、（N〜3^n個あれば、それは2Nが行く〜かかります）O（2log_3N）時間で動作します：3 による除算：

• n個のmod 3 == 0
• n個のmod 3 == 1：減算1
• n個のmod 3 == 2：1

は、私たちは私たちが行う必要が3倍、によって減らすために最大で2点の移動を必要とする追加〜N回。

<input type='number' id='nm'/> 
 
<button onclick='go();'>Go</button> 
 
<br> 
 
<span id='out'/> 
 
<script> 
 

 
function go() { 
 
var n=nm.value; 
 
var nc=0; 
 
out.textContent=n; 
 
while (n>1) { 
 
    n3=n%3; 
 
    switch (n3) { 
 
     case 0: {n/=3;break;} 
 
     case 1: {n--;break;} 
 
     case 2: {n++;break;} 
 
    } 
 
    nc++; 
 
    out.textContent+=','+ n; 
 
    } 
 
out.textContent+=' ::'+ nc; 
 
} 
 

 
</script>