[Codeforces] Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits

2020年9月8日2020年12月13日

問題

方針

イメージとしては下位の桁の数字を \( 0 \) にしていくためのコストから計算していきます。

自然数 \( n \) の桁和を \( f(n) \) とします。自然数 \( n, s \) が与えられたとき、

\[ f(n + x) \leq s\]

を満たす \( 0 \) 以上の最小の整数 \( x \) を求めます。これは \( n \) の下位の桁から見ていくことで解くことができます。\( n \) の \( i \) 桁目の数字を \( n_i \) とします。このとき、

\[ f(n + 10 – n_1) \leq  f(n)\]

が成り立ちます。これは、\( n + 10 – n_1 \) の \( 1 \) 桁目が \( 0 \) となるからです。同様に \( 2 \) 桁目以降について調べるために、\( n \leftarrow n + 10 – n_1 \) と更新します。また、\( n \) の \( i \) 桁目の数字は、

\[n_i = \left \lfloor \dfrac{n}{10^{i – 1}} \right \rfloor \bmod 10 \]

と計算できるので、\( n \leftarrow n + 10^{i-1}(10 – n_i) \) と更新されます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int digit_sum(ll n) {
    int ret = 0;
    while (n) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}

ll solve(ll n, int s) {
    ll t = n;
    ll a = 1;
    while (digit_sum(t) > s) {
        t += a * (10 - (t / a) % 10);
        a *= 10;
    }
    return t - n;
}

int main() {
    int t, s;
    cin >> t;
    ll n;
    ll ans[t];
    for (int i = 0; i < t; i++) {
        cin >> n >> s;
        ans[i] = solve(n, s);
    }
    for (ll i : ans) {
        cout << i << "\n";
    }
    return 0;
}