問題

整数屋さんでは $1$ 以上 ${10}^{9}$ 以下の整数が売られている。整数 $n$ の値段は $n$ を10進法表記したときの各位の和を $d(n)$ とするとき、 $a \times n + b \times d(n)$ 円である。

所持金が $x$ 円のとき、購入可能な最大の整数を求めよ。

入力

1行に整数 $a, b, n$ が順に与えられる。

条件

$1 \leq a, b \leq {10}^{9}$
$a + b \leq x \leq {10}^{18}$

出力

答えとなる整数を1行に出力すること。

解法

「整数の大きい方から順に $a \times n + b \times d(n)$ を計算し、初めて $x$ 以下であるもの」を探索していくという方法がまずは考えられます。しかし、考える整数の範囲は $1$ 以上 ${10}^{9}$ 以下のすべてであるので、値によっては実行時間制限に間に合いません。

ここで、各整数によって $d(n)$ の値が異なってくることから、 $d(n)$ の値を固定することを考えます。

固定した値を $d(n) = d$ とすると、求める整数 $n$ については \begin{align} a \times n + b \times d \leq x \end{align} が成立するので、 \begin{align} n \leq \frac{x - b \times d}{a} \end{align} が言えます。

従って、この右辺の値以下の整数で、 $d(n) = d$ であるものの最大値を探索することにより、このときの答えを求めることができます。

ここで、 $d(n) \leq d$ としても、特に問題はありません。というのも、 $d(n) \leq d$ のとき、 \begin{align} a \times n + b \times d(n) \leq a \times n + b \times d \leq x \end{align} が成立するためです。以上から、先程の不等式の右辺の値以下の整数のうち、 $d(n) \leq d$ であるものの最大値を探索すれば、 $d(n) \leq d$ であるものの最大値を求めることができます。

従って、次に $y$ を整数として、 $n \leq y$ かつ $d(n) \leq d$ である $n$ の最大値を求める方法を考えます。整数の最大値としては ${10}^{9}$ であることから、これは以下の手順によって求められます。

「現在の数値」として $0$ を、「現在の桁数」として ${10}^{9}$ を、「残りの桁の和」として $d$ を保持する
からまでの整数について、大きい方から順に以下の条件を同時に満たすものを探索する
- $i$ が「残りの桁の和」以下である
- 「（現在の数値） $+ i \times$ （現在の桁数）」が $y$ 以下である
上記の条件を満たす整数を用いて、以下のように数値を更新する
- 「現在の数値」を「（現在の数値） $+ i \times$ （現在の桁数）」に更新する
- 「現在の桁数」を「（現在の桁数） $/ 10$ 」に更新する
- 「残りの桁の和」を「（残りの桁の和） $- i$ 」に更新する
手順2, 3を「現在の桁数」が $1$ になるまで繰り返す

以上の手順を踏むことにより、「 $y$ 以下になるようにしながら、上の方の桁に大きい数字を詰めていく」ということが可能になります。また、手順2, 3を繰り返す回数は多くて10回程度で、手順2でのループ回数も最大で10回なので、 $d$ の値が与えられれば、最大値も $O(100)$ 程度で求めることができます。

さて、この問題では売られている整数は $1$ 以上 ${10}^{9}$ 以下であるので、 $d(n)$ の値として考えられる最大値は $n = 999999999$ のときの $d(n) = 81$ となります。

従って、 $1 \leq d \leq 81$ のすべての整数 $d$ について、整数 $y$ の値を求め、以上の手順を踏むことにより、 $O(8100)$ 程度の計算量で整数の最大値を求めることができます。

ソースコード

まずは、 $n \leq y$ かつ $d(n) \leq d$ である整数 $n$ の最大値を求める関数 solve() を以下のように実装しました。

ll solve(ll digit_sum, ll max_value) { // digit_sum が d（桁の和）、max_value が y （最大値）を表す
  ll ans = 0, digit = ll(1e9); // ans は最終的に導かれる最大値を、digit は「現在の桁数」をそれぞれ表す

  while (digit > 0) {
    // 9 から 0 の順で条件を満たすか見る（ i = 0 は必ず条件を満たす）
    for (ll i = 9; i >= 0; i--) {
      if (i <= digit_sum && ans + i * digit <= max_value) {
        digit_sum -= i; // 条件を満たす i を用いて、桁の和を引く
        ans += i * digit; // 条件を満たす i を用いて、答えを更新する
        break;
      }
    }
    digit /= 10; // 現在の桁数から 10 を割る
  }

  return ans;
}

この solve() が実装されている状態で、 main() 関数の中に答えを出力する部分を実装しました。

int main() {
  ll a, b, x;
  cin >> a >> b >> x; // 値の入力

  ll ans = 0; // 答えとなる値

  // 桁の和が 1 から 81 の場合のすべてについて、考えられる最大値を順に求めていく
  for (ll i = 1; i <= 81; i++) {
    ll rest = (x - b * i) / a; // 現在の値に対しての最大値 (y) を求める
    if (rest <= 0) { // もし0以下になる場合は、買える整数が無いので次の値について見る
      continue;
    }
    ans = max(ans, solve(i, min(rest, ll(1e9)))); // 買える整数の最大は 10^9 であるので、引数に注意して値を更新する
  }

  cout << ans << endl; // 答えの出力

  return 0;
}