まず、\(10^{9}\) が買うことができるかどうか試します。買えたらそれが答えです。

買えない場合、 \(10^{8}\) の桁、 \(10^{7}\) の桁、… 、\(10^{0}\) の桁の順にその桁の数字を決めます。

\(10^{x}\) の桁の数が \(y\) のときその桁に対して払う金額は \(y(A10^{x}+B)\) なので、 \(y=0,1,...,9\) の対して、\(10^{x}\) の桁の数が \(y\)であるような数を買えるかどうかを調べます。

買えるもののうち最大の \(y\) が決まったら、 \(X\leftarrow (X-y(A10^{x}+B))\) と更新して下の桁を見ます。

このように上の桁から貪欲に決めることで答えが求まります。

実装例 c++

実装例 pypy3