当前位置: 代码迷 >> 综合 >> codeforces1373E. Sum of Digits
  详细解决方案

codeforces1373E. Sum of Digits

热度:64   发布时间:2023-11-24 00:30:37.0

题意:定义f(x)为x的所有数位和,给定n(0=<n<=150)和k(0<=k<=9),求满足f(x)+f(x+1)+...+f(x+k)=n的x最小值

k<=9,可得最多一次进位,根据贪心容易知道满足题意的x必定为xx999x的形式,即从十位开始有若干个9,可以枚举个位数c和中间9的个数得到结果

#include <bits/stdc++.h>
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {int n, k;std::cin >> n >> k;long long ans = -1;for (int c = 0; c < 10; ++c) {for (int d = 0; 9 * d + c <= n; ++d) {int a = k + 1, b = 0;for (int i = 0; i <= k; ++i)b += (i + c) % 10 + (i + c < 10 ? 9 * d : 1);b = n - b;if (b < 0 || b % a != 0)continue;int x = b / a;long long v;if (x < 8) {v = x;}else {x -= 8;v = x % 9;x -= v;for (int i = 0; i < x / 9; ++i)v = 10 * v + 9;v = 10 * v + 8;}for (int i = 0; i < d; ++i)v = 10 * v + 9;v = 10 * v + c;if (v < 1e18 && (ans == -1 || v < ans))ans = v;}}std::cout << ans << "\n";}return 0;
}