問題一覧 > 通常問題

No.2241 Reach 1

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 124
作問者 : shobonvipshobonvip / テスター : noya2noya2 👑 NachiaNachia
7 ProblemId : 9135 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 20:04:08

問題文

$2$ 以上の整数 $N$ が与えられます。変数 $m$ があり、最初は $m=N$ です。

あなたはこの変数に対して、$1$ 回の操作で次のいずれかを行うことができます。

  1. $m/2^k$ が整数となるような負でない整数 $k$ を選び、$m$ を $m/2^k$ に置き換える
  2. 正の整数 $k$ を選び、$m$ を $mk+1$ に置き換える

あなたの目標は、できるだけ少ない操作回数で $m=N$ の状態から $m=1$ にすることです。目標を達成するために必要な操作回数の最小値を答えてください。

制約

  • $2 \le N \le 10^9$

入力

$N$

出力

$m=N$ から $m=1$ にするために必要な操作回数の最小値を答えてください。

なお、この制約下で目標は必ず達成でき、答えは $2^{31}-1$ 以下であることが保証されます。

サンプル

サンプル1
入力
4
出力
1

最初、$m=4$ です。

操作 1. において $k=2$ を選ぶと、$m=4/2^2=1$ になります。

$1$ 回より少なく操作をすることはできないので、$1$ 回が答えになります。

サンプル2
入力
3
出力
2

最初、$m=3$ です。

まず、操作 2. において $k=1$ を選ぶと、$m=3\times 1+1 = 4$ になります。

次に、操作 1. において $k=2$ を選ぶと、$m=4/2^2=1$ になります。

$2$ 回より少ない操作回数で $m=1$ にすることはできないので、$2$ 回が答えになります。

サンプル3
入力
6
出力
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。