Codeforces 1373E Sum of Digits【构造】

题目

Let f(x) be the sum of digits of a decimal number x.

Find the smallest non-negative integer x such that f(x) + f(x + 1) + \dots + f(x + k) = n.

Input

The first line contains one integer t (1 \le t \le 150) — the number of test cases.

Each test case consists of one line containing two integers n and k (1 \le n \le 150, 0 \le k \le 9).

Output

For each test case, print one integer without leading zeroes. If there is no such x that f(x) + f(x + 1) + \dots + f(x + k) = n, print -1; otherwise, print the minimum x meeting that constraint.

题目大意

给定 n,k,让你求最小的非负整数 x,满足 f(x)+f(x+1)+\cdots+f(x+k)=n

题解

首先,显然有 f(x) 的递推式:
f(x+1)=f(x)+1-9\cdot c
其中,c 表示 x 末尾数字9的个数

所以有:
f(x)+\cdots+f(x+k)=(k+1)\cdot f(x)+\frac{k(k+1)}{2}-9\cdot r\cdot c
其中,r 表示 \lbrace x,x+1,\dots,x+k \rbrace 中,加完对应数字之后发生了进位的数字的个数;c 表示恰好没有发生进位的数字末尾的9的个数,如果根本没有数字发生进位,则 c=0

由于 r 可根据 x 的个位和 k 计算得到,所以只需枚举 x 的个位数字 a 以及9的个数 c,当 a,c 确定时,可解出此时的 f(x),此时需要根据 f(x) 的值,构造出符合条件的最小的 x

构造方法:x 的形式为"?99...99899...99a",其中后半部分9的个数为 c-1,前半部分的"?"的值以及9的个数则根据 f(x) 的值确定。这样的贪心构造可以确保此时的 x 最小

每次枚举时,用当前 x 更新答案即可

需要注意的是,枚举过程中,需要确保所有中间结果符合相应约束条件(如为正整数、大于0等,在此不详细叙述),否则该枚举状态不合法,舍弃即可

Code

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int T, n, K;

int cmp(string &a, string &b) {
    if (a.size() != b.size()) {
        return a.size() - b.size();
    }
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            return a[i] - b[i];
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> K;
        string ans = "-1";
        for (int c = 0; c <= 20; c++) {
            for (int a = 0; a <= 9; a++) {
                if (c == 0 && a + K >= 10) {
                    continue;
                }
                int r = max(0, K + 1 - (10 - a));
                int u = n - K * (K + 1) / 2 + 9 * c * r, d = K + 1;
                if (u >= 0 && !(u % d)) {
                    int f = u / d;
                    int rest = f - a;
                    string s = string(1, a + '0');
                    if (c >= 2) {
                        rest -= 9 * (c - 1);
                        s = string(c - 1, '9') + s;
                    }
                    if (rest >= 0) {
                        if (rest <= 8) {
                            if (rest > 0) {
                                s = (char)(rest + '0') + s;
                            }
                        } else {
                            s = "8" + s;
                            rest -= 8;
                            if (rest / 9) {
                                s = string(rest / 9, '9') + s;
                            }
                            if (rest % 9) {
                                s = (char)(rest % 9 + '0') + s;
                            }
                        }
                        if (ans == "-1" || cmp(s, ans) < 0) {
                            ans = s;
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注