問題一覧 > 通常問題

No.3038 シャッフルの再現

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 138
作問者 : Blue_S / テスター : eiram Nauclhlt🪷 naniwazu
0 ProblemId : 11809 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-26 18:29:10

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。