Andrew Stankevich’s Contest #6解题报告 » ZOJ2599

ZOJ2599
ZOJ2599.cpp


#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

long long c[20][200];
long long s[20][200];
long long o[200][20];
long long x[200][20];

void init() {
	c[0][0] = o[0][0] = 1LL;
	for (int i = 1; i < 20; ++i) {
		for (int j = 0; j < 200; ++j) {
			for (int k = 0; k < 10 && k <= j; ++k) {
				c[i][j] += c[i - 1][j - k];
			}
			o[j][i] = c[i][j];
		}
	}
	for (int i = 0; i < 20; ++i) {
		partial_sum(c[i], c[i + 1] - 1, s[i] + 1);
	}
	for (int j = 0; j < 200; ++j) {
		partial_sum(o[j], o[j + 1] - 1, x[j] + 1);
	}
}

vector<int> digits(long long n) {
	vector<int> ret;
	while (n > 0) {
		ret.push_back(n % 10);
		n /= 10;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

int digitsum(long long n) {
	vector<int> d = digits(n);
	return accumulate(d.begin(), d.end(), 0);
}

long long sum_less(int s, const vector<int>& d) {
	long long ret = ::s[d.size() - 1][s] - 1;
	for (int i = 0; i < (int)d.size(); ++i) {
		for (int j = (i == 0 ? 1 : 0); j < d[i]; ++j) {
			if (s >= j) {
				ret += ::s[d.size() - i - 1][s - j];
			}
		}
		s -= d[i];
	}
	return ret;
}

long long lex_less(int s, const vector<int>& k, const vector<int>& d) {
	int x;
	long long ret = 0;

	// length <
	x = s;
	for (int i = 0; i < (int)k.size(); ++i) {
		if (x == 0) {	// prefix
			++ret;
		}
		for (int j = (i == 0 ? 1 : 0); j < k[i]; ++j) {
			if (x >= j) {
				ret += ::x[x - j][d.size() - i - 1];
			}
		}
		x -= k[i];
	}

	// length ==
	if (k < d) {
		x = s;
		for (int i = 0; i < (int)k.size(); ++i) {
			for (int j = (i == 0 ? 1 : 0); j < k[i]; ++j) {
				if (x >= j) {
					ret += ::o[x - j][d.size() - i - 1];
				}
			}
			x -= k[i];
		}
	} else {
		x = s;
		for (int i = 0; i < (int)d.size(); ++i) {
			for (int j = (i == 0 ? 1 : 0); j < d[i]; ++j) {
				if (x >= j) {
					ret += ::o[x - j][d.size() - i - 1];
				}
			}
			x -= d[i];
		}
	}

	return ret;
}

int main() {
	int ds, l, r, m;
	long long n, k;
	vector<int> dn, dk;

	init();
/*
	n = 1024;
	vector<long long> ans(n, -1);
	for (int i = 1; i <= n; ++i) {
		long long idx = sum_less(digitsum(i), digits(n + 1)) + lex_less(digitsum(i), digits(i), digits(n + 1));
		if (ans[idx] != -1) {
			printf("ERROR: [%4lld] = %-4lld (%d) [%d]\n", idx, ans[idx], digitsum(ans[idx]), i);
		}
		ans[idx] = i;
	}
	for (int i = 0; i < n; ++i) {
		printf("[%4d] = %-4lld (%d)\n", i, ans[i], digitsum(ans[i]));
	}
*/
	while (scanf("%lld%lld", &n, &k) != EOF && n > 0) {
		ds = digitsum(k);
		dn = digits(n + 1);
		dk = digits(k);
		printf("%lld ", 1 + sum_less(ds, dn) + lex_less(ds, dk, dn));

		l = 0;
		r = 200;
		while (l < r) {
			m = (l + r) / 2;
			if (sum_less(m, dn) < k) {
				l = m + 1;
			} else {
				r = m;
			}
		}
		m = r - 1;

		k -= sum_less(m, dn);
		dk.clear();
		while (dk.size() <= dn.size()) {
			dk.push_back(9);
			while (dk.back() >= 0 && lex_less(m, dk, dn) >= k) {
				--dk.back();
			}
			if (dk.back() == -1) {
				break;
			}
		}
		dk.pop_back();

		for (int i = 0; i < (int)dk.size(); ++i) {
			printf("%d", dk[i]);
		}
		puts("");
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//2248811 	2010-08-02 08:41:38 	Accepted 	2599 	C++ 	0 	300 	watashi@Zodiac 	Source
Leave a Reply