[EC Final 2022] Best Carry Player 2

形式化题目

把 $x$ 从低位到高位写成 $a_0, a_1, \ldots, a_{n-1}$ （ $a_0$ 是个位， $n \leqslant 18$ ），把 $y$ 的同位数字写成 $b_i$ ，把第 $i$ 位向第 $i+1$ 位的进位记作 $c_{i+1}$ ，其中 $c_0 = 0$ 。竖式加法的规则就是

c_{i+1} = 1 \iff a_i + b_i + c_i \geqslant 10 .

要求进位次数 $|\{i : c_{i+1} = 1\}|$ 恰好等于 $k$ ，在所有满足条件的正整数 $y = \sum_i b_i 10^i$ 中求最小值；不存在满足条件的 $y$ 时输出 $-1$ 。

注意 $y$ 可以比 $x$ 长，此时更高位的 $a_i$ 视为 $0$ ；最高位之外悬挂的最终进位不计入次数。

以样例第三、四组为例：

$x = 12345678,\ k = 18$ ，答案 $y = 999999999987654322$ ，此时每一位都在进位，并把进位链一路延伸到 $x$ 之外；
$x = 990099,\ k = 5$ ，答案 $y = 9910$ ： $990099 + 9910 = 1000009$ ，进位发生在第 $1 \sim 5$ 位，其中第 $4,5$ 位是 $9$ ，靠 $b_4 = b_5 = 0$ 白拿进位。

暴力解法

思路

最直接的做法就是从小到大枚举 $y = 1, 2, 3, \ldots$ ，对每个 $y$ 做一次竖式模拟：用一个变量 c 记录进位、cnt 记录进位次数，只要 $x$ 或 $y$ 还有位就继续，检查 x % 10 + y % 10 + c 是否达到 $10$ ；达到就 cnt++ 且 c = 1，否则 c = 0。第一次 cnt == k 时输出这个 $y$ 。

循环结束后若还剩进位，那是最高位之外的悬挂进位，题目不计入，所以不再额外加一。brute.cpp 把枚举上限设为 LIMIT，超过上限仍未找到就输出 -1；这在本题的大答案场景下会给出错误结果，因此它只能作为小数据基线。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 12:31
 * update_at: 2026-10-03 12:31
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
//
// 直接从小到大枚举 y = 1, 2, 3, ...，
// 用竖式加法逐位模拟 x + y，统计 a[i] + b[i] + c 达到 10 的次数，
// 第一次恰好等于 k 的 y 就是答案。
// 注意：最高位之外的悬挂进位不算「进位」，所以只在两数都处理完之前统计。
// 因为答案可能很大，枚举上限取 LIMIT；配套的 gen.py 只生成答案远小于 LIMIT 的小数据。
#include <bits/stdc++.h>
using namespace std;

const long long LIMIT = 2000000;   // 枚举上限，保证对拍数据足够小

// 统计 x + y 竖式加法的进位次数
int count_carry(long long x, long long y) {
    int c = 0;        // 当前进位
    int cnt = 0;      // 已经发生的进位次数
    while (x > 0 || y > 0) {
        int s = (int)(x % 10) + (int)(y % 10) + c;
        if (s >= 10) {
            c = 1;
            cnt++;
        } else {
            c = 0;
        }
        x /= 10;
        y /= 10;
    }
    // 循环结束后剩下的进位是最高位的悬挂进位，题目不计入
    return cnt;
}

void solve_one(long long x, int k) {
    for (long long y = 1; y <= LIMIT; y++) {
        if (count_carry(x, y) == k) {
            printf("%lld\n", y);
            return;
        }
    }
    puts("-1");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long x;
        int k;
        scanf("%lld %d", &x, &k);
        solve_one(x, k);
    }
    return 0;
}

复杂度

设答案为 $A$ ， $x$ 的位数为 $n$ ，则时间 $O(A \cdot n)$ ，额外空间 $O(1)$ 。

瓶颈

瓶颈不在模拟，而在「枚举 $y$ 的值」这件事和约束没有直接关系。进位次数是加在数位上的条件，而 $y$ 的空间大得离谱：

$x = 12345678, k = 18$ 时答案是 $999999999987654322$ ，枚举要 $10^{18}$ 次；
$x = 10^{17}, k = 18$ 时答案的位数约 $35$ ，更不可能枚举；
每组测试都要重来一次，而 $T$ 可达 $10^5$ 。

所以要换一个搜索对象：不再问「 $y$ 取多少」，而问「哪些位置产生进位」。

正解

思路

固定 $a_i$ 和进入这一位的进位 $c_i$ ，那么「这一位要不要产生进位」一旦决定，最优的 $b_i$ 就被唯一确定：为了让 $y$ 最小， $b_i$ 应该刚好够用，不用多花一分。四种情况如下。

进入进位 $c_i$	这一位产生进位	存在条件	最优 $b_i$	离开进位 $c_{i+1}$
$0$	否	无	$0$	$0$
$0$	是	$a_i \geqslant 1$	$10 - a_i$	$1$
$1$	否（进位结束）	$a_i \leqslant 8$	$0$	$0$
$1$	是（进位继续）	无	$9 - a_i$	$1$

两处条件值得单独说明：

$a_i = 0$ 时不能凭空产生进位。即使取 $b_i = 9$ ， $0 + 9 = 9$ 也进不了位，所以每个进位段的首位必须满足 $a_i \geqslant 1$ ，此时取 $b_i = 10 - a_i$ 恰好把和顶到 $10$ 。
$a_i = 9$ 时进位停不下来。 $9 + b_i + 1 \geqslant 10$ 对一切 $b_i \geqslant 0$ 都成立，无法在这一位结束进位，只能继续。这正是 $x$ 里连续的 $9$ 能「白拿」进位的原因（此时 $b_i = 9 - 9 = 0$ ）。

于是问题变成：在数位上选出恰好 $k$ 个进位位置，使 $\sum b_i 10^i$ 最小。由于进位只依赖相邻位，可以做数位 DP。设 $dp[c][j]$ 表示处理完当前位后、当前进位状态为 $c$ 、已经产生 $j$ 次进位时 $y$ 的最小值，初始 $dp[0][0] = 0$ ，按上表从低位向高位转移，第 $i$ 位的代价乘以权值 $10^i$ 。

处理完 $x$ 的 $n$ 位之后还要收尾，因为第 $n-1$ 位可能产生了进位 $c_n = 1$ ：

$dp[0][k]$ 直接是候选答案：进位已经停下，且总共恰好 $k$ 次；
若 $dp[1][j]$ 有效，进位还在往高位走。此时 $a_i = 0\ (i \geqslant n)$ ，取 $b_i = 9$ 就有 $0 + 9 + 1 = 10$ ，可以再记一次进位。还差 $rem = k - j$ 次进位，就要在第 $n \sim n+rem-1$ 位都取 $9$ ，代价为

9 \cdot (10^n + 10^{n+1} + \cdots + 10^{n+rem-1}) = 10^{n+rem} - 10^n .

$rem = 0$ 时该位取 $b_i = 0$ ，代价为 $0$ ，即让悬挂进位停下。

$k = 0$ 可以单独用 $O(n)$ 处理：此时任何一位都不能产生进位，所以最低位全部取 $0$ ，直到第一个满足 $a_i \leqslant 8$ 的位置 $i$ 取 $b_i = 10 - a_i$ （ $a_i = 0$ 时取 $0$ ），答案是 $10^i$ ；若 $x$ 全是 $9$ ，则取 $i = n$ ，答案是 $10^n$ 。例如 $x = 9$ 时答案是 $10$ ， $x = 12345678$ 时答案是 $1$ 。

用小数据检验一下状态含义。取 $x = 19$ ，则 $a = [9, 1]$ ， $k = 2$ ：

处理完	$dp[0][0]$	$dp[0][1]$	$dp[0][2]$	$dp[1][0]$	$dp[1][1]$	$dp[1][2]$
初始	$0$	–	–	–	–	–
$i=0,\ a_0=9$	$0$	–	–	–	$1$	–
$i=1,\ a_1=1$	$0$	$1$	–	–	$90$	$81$

表中 -- 表示不可达。逐格读法：

$i=0$ ：个位取 $b_0 = 0$ 得到 $dp[0][0] = 0$ ； $a_0 = 9 \geqslant 1$ ，取 $b_0 = 10 - 9 = 1$ 新开一次进位，得到 $dp[1][1] = 1$ ，对应 $y$ 的个位是 $1$ 。
$i=1$ ：从 $dp[0][0]$ 不进位仍是 $0$ ；从 $dp[1][1]$ 结束进位（ $a_1 = 1 \leqslant 8$ ， $b_1 = 0$ ）得到 $dp[0][1] = 1$ ；从 $dp[0][0]$ 在十位新开进位得 $10 - 1 = 9$ ，代价 $9 \times 10 = 90$ ，得到 $dp[1][1] = 90$ ；从 $dp[1][1]$ 继续进位得 $9 - 1 = 8$ ，代价 $1 + 8 \times 10 = 81$ ，得到 $dp[1][2] = 81$ 。

结尾 $dp[0][2]$ 不可达，只需比较两个进位未停的状态：

$j = 1$ ，还差 $rem = 1$ 次进位， $90 + (10^3 - 10^2) = 990$ 。此时 $y = 990$ ， $19 + 990 = 1009$ ，进位发生在十位和百位，恰好两次，合法。
$j = 2$ ， $rem = 0$ ， $81 + (10^2 - 10^2) = 81$ 。此时 $y = 81$ ， $19 + 81 = 100$ ，两次进位，同样合法。

两者都合法，取最小值 $81$ 。这个例子也说明尾部公式不能漏： $y = 990$ 的进位是越过 $x$ 的最高位后在更高位补足出来的。

答案最大时约有 $35$ 位十进制数（ $x = 10^{17},\ k = 18$ ），超过 long long，所以实现里用 unsigned __int128 保存状态值，并手写十进制输出。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-03 12:31
 * update_at: 2026-10-03 12:31
 */
// P9718 [EC Final 2022] Best Carry Player 2
// 求最小的正整数 y，使 x + y 的竖式加法中「进位次数」恰好为 k，无解输出 -1。
//
// 核心模型：把 x 从低位到高位写成 a[0..n-1]，y 的同位数字记作 b[i]。
// 设 c[i] 表示第 i 位向第 i+1 位的进位（c[0]=0），则
//   c[i+1] = 1 等价于 a[i] + b[i] + c[i] >= 10。
// 于是「进位次数」= 进位集合 { i : c[i+1]=1 } 的大小。
//
// 一个位置要想「新产生」进位，必须 a[i] + c[i] + b[i] >= 10，即
//   - c[i]=0 时需要 a[i] >= 1，最小 b[i] = 10 - a[i]（把和顶到 10）；
//   - c[i]=1 时需要 b[i] >= 9 - a[i]，最小 b[i] = 9 - a[i]。
// 注意 c[i]=0 且 a[i]=0 时即使 b[i]=9 也只能得到 9，无法产生进位，
// 所以每个进位段的首位必须满足 a[i] >= 1。
// 同理，「进位到此为止」需要 a[i] + b[i] + c[i] <= 9：
//   - c[i]=1 时最小代价 b[i]=0，且要求 a[i] <= 8（a[i]=9 时无法停下）。
//
// 于是问题变成：在数位上选出恰好 k 个进位位置，使 y 的值最小。
// 用 dp[c][j] = 处理完前 i 位后、当前进位状态为 c、已产生 j 次进位时 y 的最小值，
// 从低位向高位转移即可；每一位的代价 b[i] 会乘以 10^i。
// 超出 x 长度的位置 a[i]=0，此时：
//   - c=0 什么也不做，代价 0；
//   - c=1 一路继续 j' 位，最小 y 是 1 后跟 (n + j') 个 0（即 10^(n+j')）。
// 答案可能达到 10^36 量级，用 unsigned __int128 存下绰绰有余。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 20;      // x < 10^18，位数不超过 18
const int MAXK = 20;      // k <= 18
const int MAXP = 45;      // 10^36 < 2^128，够用

unsigned __int128 pow10u[MAXP];              // pow10u[i] = 10^i
unsigned __int128 dp[2][MAXK];               // dp[进位状态][已用进位次数]
unsigned __int128 ndp[2][MAXK];
int a[MAXN + 1];                             // x 从低到高的各位数字
int n;                                       // x 的位数

const unsigned __int128 U128_INF = ~(unsigned __int128)0;

// unsigned __int128 没有现成的输出，手动转十进制
void print_u128(unsigned __int128 v) {
    char s[64];
    int len = 0;
    if (v == 0) {
        putchar('0');
        return;
    }
    while (v > 0) {
        s[len++] = char('0' + (int)(v % 10));
        v /= 10;
    }
    while (len > 0) {
        putchar(s[--len]);
    }
}

// 拆出 x 的每一位，a[0] 是最低位
void split_digits(unsigned long long x) {
    n = 0;
    while (x > 0) {
        a[n++] = (int)(x % 10);
        x /= 10;
    }
    if (n == 0) {
        a[n++] = 0;
    }
}

void solve_one(unsigned long long x, int k) {
    split_digits(x);

    // k = 0 的情况：y 的每一位都不能和 x 产生进位
    // 只要某一位 a[i] <= 8，该位取 b[i] = 10 - a[i]（a[i]=0 时取 0）即可，
    // 更低的位全部取 0，所以答案是 10^i（i 是最小的满足 a[i] <= 8 的下标）。
    // 若 x 全是 9，则取 y = 10^n，此时 a[i]=0（i=n）满足条件。
    if (k == 0) {
        int i = 0;
        while (i < n && a[i] == 9) {
            i++;
        }
        print_u128(pow10u[i]);
        putchar('\n');
        return;
    }

    // 初始：还没处理任何位，进位状态 0，已用 0 次进位，y 的值 0
    for (int c = 0; c < 2; c++) {
        for (int j = 0; j <= k; j++) {
            dp[c][j] = U128_INF;
        }
    }
    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 2; c++) {
            for (int j = 0; j <= k; j++) {
                ndp[c][j] = U128_INF;
            }
        }
        unsigned __int128 w = pow10u[i];   // 第 i 位的权值
        for (int c = 0; c < 2; c++) {
            for (int j = 0; j <= k; j++) {
                if (dp[c][j] == U128_INF) {
                    continue;
                }
                if (c == 0) {
                    // 不产生进位：b[i] = 0
                    if (dp[c][j] < ndp[0][j]) {
                        ndp[0][j] = dp[c][j];
                    }
                    // 新产生一次进位：要求 a[i] >= 1，b[i] = 10 - a[i]
                    if (a[i] >= 1 && j + 1 <= k) {
                        unsigned __int128 val = dp[c][j] + (unsigned __int128)(10 - a[i]) * w;
                        if (val < ndp[1][j + 1]) {
                            ndp[1][j + 1] = val;
                        }
                    }
                } else {
                    // 进位结束：要求 a[i] <= 8，b[i] = 0
                    if (a[i] <= 8 && dp[c][j] < ndp[0][j]) {
                        ndp[0][j] = dp[c][j];
                    }
                    // 进位继续：b[i] = 9 - a[i]，又产生一次进位
                    if (j + 1 <= k) {
                        unsigned __int128 val = dp[c][j] + (unsigned __int128)(9 - a[i]) * w;
                        if (val < ndp[1][j + 1]) {
                            ndp[1][j + 1] = val;
                        }
                    }
                }
            }
        }
        for (int c = 0; c < 2; c++) {
            for (int j = 0; j <= k; j++) {
                dp[c][j] = ndp[c][j];
            }
        }
    }

    unsigned __int128 ans = U128_INF;

    // 结尾一：不进位，必须恰好用满 k 次进位
    if (dp[0][k] < ans) {
        ans = dp[0][k];
    }

    // 结尾二：第 n-1 位产生了进位，即 c[n]=1。此时最高位之外 a[i]=0，
    // 补 b[i]=9 可以让进位继续：0 + 9 + 1 = 10，又记账一次进位。
    // 设还需要 rem = k - j 次进位，就要在第 n ~ n+rem-1 位都补 9，
    // 代价为 9 * (10^n + ... + 10^(n+rem-1)) = 10^(n+rem) - 10^n。
    // rem = 0 时代价为 0：该位取 b=0 即可让最终悬挂的进位停下。
    for (int j = 0; j <= k; j++) {
        if (dp[1][j] == U128_INF) {
            continue;
        }
        int rem = k - j;
        unsigned __int128 val = dp[1][j] + pow10u[n + rem] - pow10u[n];
        if (val < ans) {
            ans = val;
        }
    }

    if (ans == U128_INF) {
        puts("-1");
    } else {
        print_u128(ans);
        putchar('\n');
    }
}

int main() {
    pow10u[0] = 1;
    for (int i = 1; i < MAXP; i++) {
        pow10u[i] = pow10u[i - 1] * 10;
    }

    int T;
    scanf("%d", &T);
    while (T--) {
        unsigned long long x;
        int k;
        scanf("%llu %d", &x, &k);
        solve_one(x, k);
    }
    return 0;
}

复杂度

设 $x$ 的位数为 $n \leqslant 18$ 。单组时间 $O(nk)$ ， $k \leqslant 18$ 时不超过 $324$ 次转移； $T = 10^5$ 时总量约 $3 \times 10^7$ 。空间为常数级数组， $O(1)$ 。

总结

本题的约束写在「进位次数」上，所以搜索对象应该是进位位置的形状，而不是 $y$ 的数值；
一旦固定 $a_i$ 和进入的进位 $c_i$ ，每位的最优 $b_i$ 唯一：不进位取 $0$ ，新开进位取 $10 - a_i$ （要求 $a_i \geqslant 1$ ），进位继续取 $9 - a_i$ ，结束进位取 $0$ （要求 $a_i \leqslant 8$ ）；
把「当前进位状态」和「已用进位次数」作为 DP 的两维，就能在 $O(nk)$ 内求出最小 $y$ ； $x$ 之外的位用 $10^{n+rem} - 10^n$ 公式一次性补齐；
答案可达 $10^{35}$ ，C++ 里要想到 unsigned __int128（或手写高精度），这是本题最常见的失分点。