問題一覧 > 通常問題

No.3038 Reproducing the Shuffle

レベル : / AI推定難易度 : 120 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 149
作問者 : Blue_S / テスター : eiram nauclhlt naniwazu
お気に入りにしたユーザー ProblemId : 11809 / 自分の提出
問題文最終更新日: 2025-02-26 18:29:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 458 (順位表) の他の問題:

Problem Statement

There is a stack of cards with the numbers from $1$ to $N$ written on them, piled in numerical order so that $1$ is on top and $N$ is on the bottom. This state is called the initial state.

These cards are to be shuffled, and there are the following 2 kinds of shuffles.
Swap shuffle: swap two vertically adjacent cards
Magician shuffle: take the top card and insert it somewhere between the other cards

For example, when the cards are $3, 4, 2, 1$ from the top, a swap shuffle can produce any one of the states $4, 3, 2, 1$ and $3, 2, 4, 1$ and $3, 4, 1, 2$, and a magician shuffle can produce any one of the states $4, 3, 2, 1$ and $4, 2, 3, 1$ and $4, 2, 1, 3$.

Starting from the initial state, eiram performed a magician shuffle that inserted the top card between the cards with $K$ and $K + 1$ written on them.
nauclhlt likes going against the crowd, so he decided to try reproducing the same state from the initial state using only swap shuffles. What is the minimum number of swap shuffles required?

Input

$N\ K$

$3 \le N \le 10^{10}$
$2 \le K \lt N$

Output

$ans$

Print a newline at the end.

Sample

Sample 1
Input
5 3
Output
2

Initially the cards are $(1, 2, 3, 4, 5)$ and the target arrangement is $(2, 3, 1, 4, 5)$.
It suffices to go through $(2, 1, 3, 4, 5)$ and $(2, 3, 1, 4, 5)$, so it can be done in 2 moves. This is the minimum.

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