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;
}