MDIGITS - Counting Digits

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int p10[10];

struct Result {
	int a[10];

	Result(const int &v = 0, const int &n = 10) {
		memset(a, 0, sizeof a);
		for(int i = 0; i < n; ++i)
			a[i] = v;
	}

	Result operator * (const int &x) const {
		Result res = *this;
		for(int i = 0; i < 10; ++i)
			res.a[i] *= x;
		return res;
	}

	Result operator + (Result r) const {
		for(int i = 0; i < 10; ++i)
			r.a[i] += a[i];
		return r;
	}

	Result operator - (Result r) const {
		for(int i = 0; i < 10; ++i)
			r.a[i] = a[i] - r.a[i];
		return r;
	}

	void print() const {
		printf("%d", a[0]);
		for(int i = 1; i < 10; ++i)
			printf(" %d", a[i]);
		printf("\n");
	}
} c[10];

void init() {
	p10[0] = 1;
	for(int i = 1; i < 10; ++i)
		p10[i] = p10[i-1] * 10;
	for(int i = 1; i < 10; ++i) {
		c[i] = (c[i-1] * 10) + (Result(1) * p10[i-1]);
	}
}

char s[10];
Result calc(int x) {
	sprintf(s, "%d", x);
	int n = strlen(s);
	Result res, temp;
	for(int i = 0; i < n; ++i) {
		res = res + c[n-i-1] * (s[i] - 0x30);
		res = res + (temp * (s[i] - 0x30) + Result(1, s[i] - 0x30)) * p10[n-i-1];
		++temp.a[s[i]-0x30];
	}
	res = res + temp;
	return res;
}

Result one(int x) {
	Result res;
	for(; x != 0; x /= 10) ++res.a[x%10];
	return res;
}

int main() {
	init();
	for(int x, y; scanf("%d%d", &x, &y) == 2 && (x | y); ) {
		if(x > y) swap(x, y);
		Result res;
		while(x <= y) {
			res = res + one(x);
			res = res + calc(min(y, *upper_bound(p10, p10+10, x) - 1)) - calc(x);
			x = *upper_bound(p10, p10+10, x);
		}
		res.print();
	}
	return 0;
}

Download