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$ つめのテストケースのみ。

入力を受け取る。

x: 11
y: 9
k: 3

まず、x を $3$ 進法に変換する。
$11 = 1\times 3^2 + 0\times 3^1 + 2\times 3^0$ なので、正順に直した後の数字列は次のようになる。

x_vec: {1, 0, 2}

次に、y を $3$ 進法に変換する。
$9 = 1\times 3^2 + 0\times 3^1 + 0\times 3^0$ なので、正順に直した後の数字列は次のようになる。

y_vec: {1, 0, 0}

x_vec と y_vec が上から何個一致しているかを求める。
先頭から $2$ 個が一致しているので、d は $2$ である。

d: 2

あとは、x_vec の不一致部分を削除し、y_vec の不一致部分を追加する回数を数える。
x_vec の長さは $3$、y_vec の長さも $3$ なので、答えは $3+3-2\times 2=2$ である。

result: 2

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

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

特になし。