[Codeforces] Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits
問題
方針
イメージとしては下位の桁の数字を \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません