No.3038 シャッフルの再現
タグ : / 解いたユーザー数 138
作問者 :


問題文
$1$
から
$N$
までの数が書かれたカードが、
$1$
が上で
$N$
が下になるように
番号順に積まれています。
この状態を初期状態と呼びます。
このカードをシャッフルしますが、以下の2種類のシャッフル方法があります。
入れ替えシャッフル:上下に重なっているカードを入れ替える
マジシャンシャッフル: 一番上のカードをとってどこかの間に入れる
例えばカードの状態が上から $3, 4, 2, 1$ となっているときは、入れ替えシャッフルをすることで
$4, 3, 2, 1$と$3, 2, 4, 1$と$3, 4, 1, 2$ のどれかの状態にすることができ、
マジシャンシャッフルをすることで$4, 3, 2, 1$と$4, 2, 3, 1$と$4, 2, 1, 3$のどれかの状態にすることができます。
eiramくんは、初期状態から一番上のカードを
$K$
と
$K + 1$
の書かれたカードの間に入れるマジシャンシャッフルをしました。
nauclhltくんは、逆張りが好きなので同じ状態を初期状態から入れ替えシャッフルだけで再現してみようと思いました。
最低で何回の入れ替えシャッフルをする必要がありますか。
入力
$N\ K$
$3 \le N \le 10^{10}$
$2 \le K \lt N$
出力
$ans$
最後に改行してください。
サンプル
サンプル1
入力
5 3
出力
2
最初は
$(1, 2, 3, 4, 5)$
となっており、目標となる形は
$(2, 3, 1, 4, 5)$
です。
$(2, 1, 3, 4, 5)$
、
$(2, 3, 1, 4, 5)$
とすれば良いので、2手でできます。これが最短です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。