[AGC011E] Increasing Numbers

非常神秘。

考虑一个上升数一定可以拆分成不超过九个形如 \(111...(\texttt{k个1})={10^k-1\over 9}\) 的数之和，我们考虑用九个数 \(\{a_1,a_2,...,a_9\}\) 来表示一个上升数（被拆分成 \(a_1\) 个 \(1\) 加上 \(a_2\) 个 \(1\)......）。

设 \(n\) 被拆分成了 \(k\) 个上升数的和，我们有：

考虑到答案不会很大，我们枚举 \(k\) 来判断能否有一个合法拆分。容易（?）发现，当不进位时数位和均最大为 \(9k\)，每次进位数位和会减 \(9\)，所以合法的 \(k\) 左边的数位和一定是小于 \(9k\) 的 \(9\) 的倍数，暴力加即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int num[N], n = 0;

int main() {
	char ch = getchar();
	while (isdigit(ch)) num[++n] = ch & 15, ch = getchar();
	reverse(num + 1, num + n + 1);
	int j = 0;
	for (int i = 1; i <= n; ++i) {
		num[i] = num[i] * 9 + j;
		j = num[i] / 10;
		num[i] %= 10;
	} if (j) num[++n] = j;
	int k = 0, sum = 0;
	for (int i = 1; i <= n; ++i) sum += num[i];
	while (1) {
		++k;
		num[1] += 9; sum += 9;
		for (int i = 1; i <= n; ++i) {
			if (num[i] >= 10) ++num[i + 1], num[i] -= 10, sum -= 9;
			else break;
		} if (num[n + 1]) ++n;
		if (sum <= 9 * k) {
			printf("%d\n", k);
			return 0;
		}
	} return 0;
}