ABC465 D - X to Y

XからYへ

考え方

数式をちゃんと言語化できれば非常に単純な問題。

$\lfloor x/K \rfloor$ は、$K$ で割って切り捨て。
これが仮に $K=10$ だったら、普通に一の位を消す操作になる。
つまり、$K=10$ の場合に言っていることは、以下のようなことである。

こう考えると $K=10$ の場合答えは明らか。
$X$ と $Y$ で、先頭からの数字列が何桁共通しているかを調べればよい。
$X$ の不一致部分を全部削除して、$Y$ の不一致部分を全部追加する、その操作数の和が答え。

では、$K$ が $10$ 以外の数だったらどうするのか？
答えは単純で、$K$ 進法で扱えばいいだけである。

$1$ テストケースあたりの計算量は $O(\log_K(X+1)+\log_K(Y+1))$ である。

入力を受け取る。
$1$ つめのテストケースのみを見る。

x: 11
y: 9
k: 3

$11$ と $9$ を $3$ 進法で表すと、次のようになる。

11: 102
 9: 100

先頭の 10 までが共通している。
したがって、102 の末尾の 2 を削除し、その後 0 を追加すればよい。

実際の値では、次の $2$ 回の操作になる。

11 -> 3 -> 9
102 -> 10 -> 100  （3進法）

よって、答えは $2$ である。

$X$、$Y$、$K$ は、int 型からはみ出る。
long long 型を用いること。

また、0 を $K$ 進法変換したとき、数字列を空として扱う。
これにより、0 から正の整数へ移る場合の回数を正しく数えられる。

特になし。